Leaders in an Array

+10

Kamu mendapatkan sebuah array bilangan bulat nums. Sebuah elemen disebut pemimpin jika nilainya lebih besar dari atau sama dengan setiap elemen di sebelah kanannya. Elemen terakhir tidak memiliki elemen di sebelah kanannya, jadi elemen itu selalu menjadi pemimpin. Kembalikan semua pemimpin sesuai urutannya dalam nums, dari kiri ke kanan.

Fungsi

leaders(nums: integer-array) → integer-array

numsinteger-array: array bilangan bulat yang akan ditelusuri
Mengembalikaninteger-array: elemen pemimpin dari nums, dari kiri ke kanan

Batasan

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

Contoh

Input: nums = [12, 5, 9, 3, 6, 2]
Output: [12, 9, 6, 2]
Penjelasan: 2 berada di posisi terakhir, jadi 2 yang memimpin. 6 mengalahkan 2 yang ada setelahnya, 9 mengalahkan 3, 6, dan 2, lalu 12 mengalahkan semuanya. 5 kalah dari 9 dan 3 kalah dari 6, jadi jawabannya adalah [12, 9, 6, 2].

Pertanyaan lanjutan

Jika nilai-nilai datang satu per satu dan setelah masing-masing kamu harus melaporkan nilai terbesar sejauh ini, bagaimana kamu memperbarui list dalam waktu amortisasi O(1) per nilai?

Petunjuk

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

0 dari 3 dibuka

Solusi

Baca dari kiri, setiap elemen memerlukan pemindaian ulang terhadap sufiksnya. Telusuri dari kanan: satu-satunya hal yang perlu kamu ketahui tentang sufiks adalah nilai terbesarnya, dan satu variabel dapat menyimpannya. Cara ini mengubah pemeriksaan O(n²) menjadi satu kali lintasan.

Periksa semua yang ada di sebelah kanan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Terapkan definisinya: untuk setiap indeks i, pindai elemen-elemen setelahnya dan berhenti pada elemen pertama yang nilainya lebih besar daripada nums[i]. Jika pemindaian mencapai akhir, nums[i] adalah pemimpin. Kamu menguji indeks dari kiri ke kanan, jadi para pemimpin muncul secara berurutan. Dalam [12, 5, 9, 3, 6, 2], 5 berhenti pada 9 dan 3 berhenti pada 6.

Biayanya berasal dari pemindaian yang berlangsung sampai akhir. Dalam 24,999 nilai yang sama diikuti satu nilai yang lebih besar, setiap elemen menelusuri hampir seluruh array: sekitar 25,000 × 25,000 / 2, lebih dari 3 × 10^8 perbandingan.

Algoritma

Buat list hasil kosong.
Untuk setiap indeks i, periksa j dari i + 1 hingga akhir.
Jika ada nums[j] yang lebih besar daripada nums[i], berhenti: nums[i] bukan pemimpin.
Jika tidak ada j seperti itu, tambahkan nums[i] ke hasil.
Kembalikan hasilnya.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Satu kali lintasan dari kanan dengan nilai maksimum sementara

Intuisi

Setidaknya sebesar setiap elemen di sebelah kanan sama artinya dengan setidaknya sebesar nilai maksimum elemen-elemen tersebut. Dengan bergerak dari kanan ke kiri, kamu bisa terus memperbarui nilai maksimum itu. Elemen terakhir menjadi pemimpin dan memulai nilai maksimum. Setiap elemen di sebelah kirinya menjadi pemimpin jika nilainya setidaknya sebesar nilai maksimum, lalu menjadi nilai maksimum yang baru. Jika tidak, ada nilai yang lebih besar di sebelah kanannya.

Pada [12, 5, 9, 3, 6, 2]: 2 menjadi pemimpin, lalu 6, lalu 9, lalu 12, sedangkan 3 dan 5 berada di bawah nilai maksimum. Kamu mendapatkan [2, 6, 9, 12]; jika dibalik, itulah jawabannya.

Setiap elemen dibandingkan satu kali: waktu O(n) dan ruang ekstra O(1), selain ruang untuk hasil. Versi R menandai para pemimpin dalam vektor logical(n), jadi ruang ekstranya O(n).

Algoritma

Masukkan elemen terakhir ke dalam hasil dan tetapkan best ke elemen tersebut.
Turunkan i dari indeks kedua terakhir hingga 0.
Jika nums[i] ≥ best, tambahkan nums[i] ke dalam hasil dan tetapkan best ke elemen tersebut.
Balik urutan hasil agar elemen pemimpin terbaca dari kiri ke kanan, lalu kembalikan hasilnya.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Jebakan dan kasus tepi

Menggunakan > alih-alih ≥ saat membandingkan dengan nilai maksimum saat ini. Dalam [4, 7, 7, 1, 7], setiap 7 menjadi pemimpin, tetapi perbandingan ketat hanya mempertahankan yang terakhir.
Memulai nilai maksimum dari 0, bukan dari elemen terakhir. [-1, -5] harus mengembalikan keduanya, tetapi nilai maksimum 0 membuat keduanya tersisih.
Mengembalikan para pemimpin sesuai urutan penemuannya, [2, 6, 9, 12], bukan [12, 9, 6, 2].
Menambahkan elemen terakhir dua kali dengan memulai perulangan dari indeks terakhir setelah elemen itu sudah dimasukkan ke hasil.
Membandingkan setiap elemen hanya dengan tetangganya. Dalam [5, 3, 9], 5 lebih besar daripada 3 di sebelahnya, tetapi 9 membuat jawabannya menjadi [9].

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menemukan leader dalam array?

O(n) dengan satu kali lintasan dari kanan, karena setiap elemen dibandingkan sekali dengan nilai maksimum saat ini. Membandingkan setiap elemen dengan semua elemen di sebelah kanannya membutuhkan biaya O(n²) dalam kasus terburuk, misalnya saat semua nilainya sama.

Apakah elemen terakhir selalu menjadi pemimpin?

Ya. Sebuah elemen pemimpin harus berukuran setidaknya sama besar dengan setiap elemen di sebelah kanannya, dan elemen terakhir tidak memiliki elemen di sebelah kanannya, jadi kondisi ini terpenuhi tanpa perlu memeriksa apa pun.

Apakah nilai yang sama dihitung sebagai pemimpin?

Di sini, ya: sebuah nilai pemimpin harus lebih besar dari atau sama dengan setiap elemen di sebelah kanannya, jadi dalam [4, 7, 7, 1, 7] ketiga angka 7 menjadi nilai pemimpin. Beberapa versi meminta nilainya lebih besar secara ketat, jadi bandingkan dengan >, dan hanya nilai terakhir yang sama yang menjadi nilai pemimpin.

def leaders(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [12, 5, 9, 3, 6, 2]

Output yang diharapkan

[12, 9, 6, 2]