Find the Largest Number

Q: Berapa kompleksitas waktu untuk menemukan nilai maksimum dalam array?

Satu kali penelusuran membutuhkan waktu O(n) dan ruang ekstra O(1) . Tidak ada method pada array yang tidak diurutkan yang lebih efisien, karena elemen mana pun yang tidak pernah kamu baca bisa jadi elemen terbesar. Mengurutkan terlebih dahulu membutuhkan biaya O(n log n) .

PemulaArray dan string

+10

Kamu mendapatkan list bilangan bulat nums yang tidak kosong. Kembalikan nilai terbesar di dalamnya. Nilainya bisa negatif, jadi jawabannya juga bisa negatif. Temukan nilai itu dengan perbandinganmu sendiri, tanpa fungsi maksimum bawaan seperti max.

Fungsi

findMax(nums: integer-array) → integer

numsinteger-array: daftar bilangan bulat yang akan dicari
Mengembalikaninteger: nilai terbesar dalam nums

Batasan

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Contoh

Input: nums = [3, 17, 4, 12, 9]
Output: 17
Penjelasan: Jika dibaca dari kiri, nilai terbesar sejauh ini adalah 3, lalu 17. Tidak satu pun dari 4, 12, atau 9 yang lebih besar dari 17.

Input: nums = [-8, -3, -11, -3]
Output: -3
Penjelasan: Semua nilai bernilai negatif dan -3 paling dekat dengan nol, jadi itulah nilai terbesar. Nilai tersebut muncul dua kali, tetapi kamu mengembalikan nilainya, bukan posisinya.

Pertanyaan lanjutan

Bisakah kamu mengembalikan nilai terbesar dan terkecil dengan sekitar 3n/2 perbandingan, bukan 2n, dengan membandingkan nilai-nilai secara berpasangan terlebih dahulu?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Nilai apa pun yang kamu lewati bisa jadi yang terbesar, jadi setiap solusi membaca semua elemen. Satu kali penelusuran dengan nilai maksimum sementara sudah cukup dan tidak melakukan hal lain. Mulai nilai maksimum dari elemen pertama, jangan pernah dari 0, karena semua nilai bisa saja negatif.

Urutkan salinannya dan ambil nilai terakhir

Intuisi

Salin nums agar list pemanggil tetap seperti semula, urutkan salinannya dari yang terkecil hingga terbesar, lalu kembalikan elemen terakhirnya. Untuk [3, 17, 4, 12, 9], salinannya setelah diurutkan adalah [3, 4, 9, 12, 17].

Pengurutan menempatkan semua nilai dalam urutan tertentu, padahal kamu hanya menginginkan nilai terbesar. Ini memerlukan sekitar n log n perbandingan, kira-kira 60.000 untuk n = 5000, ditambah memori O(n) untuk salinannya.

Algoritma

Salin nums.
Urutkan salinannya dari yang terkecil hingga terbesar, dengan membandingkan angka sebagai angka.
Kembalikan elemen terakhir dari salinan yang sudah diurutkan.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Satu kali lintasan dengan nilai maksimum yang terus diperbarui

Intuisi

Simpan largest, nilai terbesar yang ditemukan sejauh ini, dan ganti nilainya setiap kali ada nilai yang lebih besar. Setelah perulangan, nilai itu sudah dibandingkan dengan setiap elemen, jadi tidak ada nilai dalam list yang lebih besar darinya. Untuk [3, 17, 4, 12, 9], nilainya dimulai dari 3, berubah menjadi 17 dan tetap begitu: n-1 perbandingan dan satu variabel tambahan.

Memulai dari nums[0] membuat list yang berisi angka negatif bisa ditangani. Jika dimulai dari 0, tidak ada nilai dalam [-8, -3, -11, -3] yang lebih besar darinya, jadi kamu mengembalikan 0, nilai yang tidak ada dalam list.

Algoritma

Tetapkan largest ke nums[0].
Lakukan perulangan untuk setiap nilai x dalam nums.
Jika x > largest, tetapkan largest ke x.
Setelah perulangan, kembalikan largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Jebakan dan kasus tepi

Mulai dari angka kecil tebakan, seperti -1000000. Nilainya bisa turun hingga -10^9, jadi [-2000000] mengembalikan tebakan tersebut. nums[0] tidak memerlukan tebakan.
Membaca nums[0] di Lua atau R, padahal elemen pertama adalah nums[1]. Lua mengembalikan nil dan R mengembalikan vektor kosong.
Melakukan perulangan dengan i ≤ n pada indeks berbasis 0, sehingga satu elemen setelah elemen terakhir terbaca.
Mengurutkan tanpa pembanding numerik di JavaScript atau TypeScript. Urutan teks dari [3, 17, 4, 12, 9] diakhiri dengan 9, jadi kamu mengembalikan 9.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk menemukan nilai maksimum dalam array?

Satu kali penelusuran membutuhkan waktu O(n) dan ruang ekstra O(1). Tidak ada method pada array yang tidak diurutkan yang lebih efisien, karena elemen mana pun yang tidak pernah kamu baca bisa jadi elemen terbesar. Mengurutkan terlebih dahulu membutuhkan biaya O(n log n).

Bagaimana cara menemukan angka terbesar dalam array tanpa menggunakan max?

Simpan elemen pertama dalam sebuah variabel. Lakukan perulangan pada elemen lainnya dan, setiap kali ada elemen yang lebih besar, simpan elemen itu sebagai gantinya. Saat perulangan berakhir, variabel tersebut menyimpan nilai terbesar.

Kapan pengurutan menjadi cara yang baik untuk menemukan nilai terbesar?

Saat kamu membutuhkan lebih dari nilai tertinggi, seperti tiga nilai terbesar atau median, dan akan mengajukan banyak pertanyaan seperti ini tentang list yang sama. Untuk mencari satu nilai maksimum, satu kali pemindaian lebih cepat dan tidak mengubah list.

def findMax(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 17, 4, 12, 9]

Output yang diharapkan