Second Largest Number
Kamu mendapatkan sebuah list bilangan bulat nums. Kembalikan nilai berbeda terbesar kedua: nilai terbesar yang lebih kecil dari nilai maksimum. Nilai bisa berulang, jadi untuk [5, 5, 3] jawabannya adalah 3, bukan 5. List tersebut selalu berisi setidaknya dua nilai yang berbeda.
Fungsi
- numsinteger-array
- daftar bilangan bulat, dengan setidaknya dua nilai yang berbeda
- Mengembalikaninteger
- nilai terbesar yang lebih kecil dari nilai maksimum
Batasan
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsberisi setidaknya dua nilai yang berbeda.
Contoh
- Input
- nums = [4, 9, 2, 7, 9]
- Output
- 7
- Penjelasan
- Nilai maksimumnya adalah
9. Nilai tersebut muncul dua kali, tetapi salinan kedua dari nilai maksimum tidak dihitung, jadi jawabannya adalah nilai berikutnya yang lebih rendah,7.
- Input
- nums = [-5, -1, -8]
- Output
- -5
- Penjelasan
- Dari yang terbesar hingga terkecil, nilainya adalah
-1,-5,-8, jadi nilai terbesar kedua adalah-5.
- Input
- nums = [6, 6, 6, 3]
- Output
- 3
- Penjelasan
- Hanya ada dua nilai yang berbeda,
6dan3. Sebanyak apa pun6diulang, nilai terbesar kedua adalah3.
Pertanyaan lanjutan
Bisakah kamu mengembalikan nilai berbeda terbesar ketiga dalam satu kali lintasan, dengan tiga variabel dan tanpa pengurutan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Untuk menemukan nilai maksimum, kamu hanya perlu satu variabel. Apa yang bisa kamu ingat dengan variabel kedua saat membaca list?
Lacak nilai terbesar dan nilai terbesar kedua yang berbeda. Nilai baru dapat mengalahkan nilai terbesar, berada di antara keduanya, atau tidak mengubah apa pun.
Atur kedua variabel di bawah ini ke setiap nilai yang diizinkan. Jika
x > largest, pindahkanlargestkeseconddan simpanx. Jika tidak, apabilaxberada di antara keduanya secara ketat, simpan nilainya disecond.
Solusi
Nilai maksimum dapat muncul berulang kali, dan kemunculan berulang tidak boleh dihitung sebagai nilai terbesar kedua. Jawabannya bisa negatif, jadi variabel yang dimulai dari 0 tidak akan berhasil jika semua nilai dalam list negatif. Satu kali pemindaian yang melacak dua nilai berbeda terbesar dengan perbandingan ketat dapat menangani keduanya.
Urutkan lalu turuni melewati nilai maksimum
Intuisi
Urutkan salinannya, lalu telusuri dari ujung ke kiri melewati setiap salinan nilai maksimum. Nilai pertama yang berbeda adalah jawabannya. Untuk [6, 6, 6, 3], kamu melewati tiga angka 6 dan sampai pada 3. Penelusuran tidak bisa melewati bagian depan, karena list berisi dua nilai yang berbeda.
Pengurutan mengurutkan setiap nilai, padahal kamu hanya memerlukan dua nilai terbesar: waktu O(n log n), ditambah memori O(n) untuk salinannya.
Algoritma
- Salin
numslalu urutkan salinannya dari yang terkecil hingga terbesar. - Mulai indeks
idi posisi terakhir. - Selama nilai di
isama dengan nilai maksimum, geserisatu langkah ke kiri. - Kembalikan nilai di
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]Dua lintasan
Intuisi
Perulangan pertama menemukan nilai maksimum. Perulangan kedua menyimpan nilai terbesar yang lebih kecil darinya. Untuk [4, 9, 2, 7, 9], perulangan pertama menemukan 9, dan perulangan kedua melewati kedua 9 lalu menyimpan 7.
Mulai dengan second di bawah setiap nilai yang diizinkan. Ada nilai yang lebih kecil dari nilai maksimum, jadi nilai awal itu selalu akan diganti. Setiap perulangan mencari nilai maksimum sementara: waktu O(n) dan ruang O(1). Membaca list dua kali adalah biayanya, dan aliran nilai yang hanya kamu lihat sekali tidak memungkinkan cara ini.
Algoritma
- Lakukan perulangan pada
numssatu kali dan simpan nilai maksimum dilargest. - Tetapkan
secondke nilai di bawah semua nilai yang diizinkan. - Lakukan perulangan lagi. Untuk setiap
xdenganx < largestdanx > second, tetapkansecondkex. - Kembalikan
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondMelacak dua nilai teratas dalam satu kali penelusuran
Intuisi
Simpan largest dan second, dua nilai berbeda terbesar sejauh ini. Nilai yang lebih besar dari largest mendorong nilai largest sebelumnya turun menjadi second. Nilai yang berada tepat di antara second dan largest menggantikan second. Selain itu, termasuk salinan lain dari largest, tidak mengubah apa pun: perbandingan ketat melewati nilai duplikat.
Untuk [4, 9, 2, 7, 9], largest menjadi 4, lalu 9 dengan second = 4. 7 berada di antara keduanya, jadi second = 7, dan 9 terakhir dilewati. Mulai kedua variabel dengan nilai yang lebih kecil daripada semua nilai yang mungkin, karena jawabannya bisa negatif. Dua nilai berbeda menjamin bahwa second berakhir dengan nilai dari list.
Algoritma
- Atur
largestdansecondke nilai di bawah semua nilai yang diizinkan. - Lakukan perulangan untuk setiap nilai
xdi dalamnums. - Jika
x > largest, pindahkanlargestkeseconddan aturlargestkex. - Jika tidak, jika
x < largestdanx > second, atursecondkex. - Setelah perulangan, kembalikan
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
Jebakan dan kasus tepi
- Mengembalikan elemen kedua dari terakhir dalam list yang sudah diurutkan. Jika nilai maksimum muncul berulang, seperti pada
[4, 9, 2, 7, 9], elemen tersebut adalah nilai maksimum lagi. - Memulai variabel dengan
0. Pada[-5, -1, -8], tidak ada nilai yang lebih besar dari0, jadi kamu mengembalikan0, yang tidak ada dalam list. - Menulis
x >= largestdalam kasus pertama. Nilai9kedua kemudian memindahkan nilai9pertama kesecond, dan kamu mengembalikan9. - Memperbarui
secondhanya saat nilai maksimum baru muncul. Dalam[10, 20, 15], nilai15tidak pernah masuk kesecond, dan kamu mengembalikan10.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu untuk menemukan elemen terbesar kedua?
Metode satu kali lintas dan dua kali lintas sama-sama memerlukan waktu O(n) dan ruang ekstra O(1); mengurutkan terlebih dahulu memerlukan O(n log n). Kamu tidak bisa mengalahkan O(n), karena setiap nilai harus dibaca satu kali.
Bagaimana duplikat memengaruhi elemen terbesar kedua?
Soal ini meminta nilai berbeda terbesar kedua, jadi nilai maksimum yang berulang dilewati: [9, 9, 7] menghasilkan 7. Beberapa versi menghitung posisi dan menjawab 9, jadi pastikan dulu versi mana yang dimaksud sebelum kamu menulis kode.
Apa yang harus kamu kembalikan ketika tidak ada nilai terbesar kedua?
Di sini hal itu tidak bisa terjadi karena list menyimpan dua nilai yang berbeda. Secara umum, list seperti [4, 4, 4] tidak memiliki jawaban: kembalikan penanda seperti -1 atau null, atau munculkan error. Kamu bisa mengetahuinya jika second masih menyimpan nilai awalnya setelah perulangan.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def secondLargest(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [4, 9, 2, 7, 9]
Output yang diharapkan
7