Kth Largest Element in an Array

Q: Berapa kompleksitas waktu untuk Elemen Terbesar ke-K dalam sebuah Array?

Pengurutan membutuhkan waktu O(n log n) . Min-heap berukuran k membutuhkan waktu O(n log k) dan memori O(k) . Quickselect dengan pivot acak membutuhkan waktu O(n) secara rata-rata dan O(n²) pada kasus terburuk, yang sangat kecil kemungkinannya terjadi dengan pivot acak.

Q: Haruskah saya menggunakan heap atau quickselect untuk menemukan elemen terbesar ke-k?

Quickselect lebih cepat secara rata-rata, O(n) , tetapi membutuhkan semua nilai di memori dan mengurutkannya ulang. Heap memiliki kompleksitas O(n log k) tanpa kasus terburuk yang buruk, dan dapat digunakan saat nilai tiba satu per satu.

SedangHeap Pengurutan

+10

Kamu mendapatkan sebuah array bilangan bulat nums dan sebuah bilangan bulat k. Kembalikan nilai terbesar ke-k di nums: nilai pada posisi k, dengan posisi dihitung mulai dari 1, setelah array diurutkan dari terbesar ke terkecil.

Nilai yang sama dihitung secara terpisah. Dalam [5, 5, 1], nilai terbesar adalah 5 dan nilai terbesar kedua juga 5.

Fungsi

findKthLargest(nums: integer-array, k: integer) → integer

numsinteger-array: nilai-nilai untuk diurutkan
kinteger: nilai terbesar yang akan dikembalikan, 1 untuk nilai terbesar
Mengembalikaninteger: nilai terbesar ke-k, termasuk nilai yang duplikat

Batasan

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Nilai yang sama dihitung sebagai nilai terpisah.

Contoh

Input: nums = [7, 2, 9, 4, 9, 1]k = 2
Output: 9
Penjelasan: Dari nilai terbesar hingga terkecil, urutannya adalah 9, 9, 7, 4, 2, 1. Kedua angka 9 dihitung secara terpisah, jadi angka terbesar kedua adalah 9, bukan 7.

Input: nums = [5, -3, 8, 0, 2]k = 4
Output: 0
Penjelasan: Dari nilai terbesar ke terkecil, urutannya adalah 8, 5, 2, 0, -3, dan nilai keempatnya adalah 0.

Input: nums = [6]k = 1
Output: 6
Penjelasan: Dengan satu nilai dan k = 1, nilai tersebut adalah yang terbesar.

Pertanyaan lanjutan

Nilai kini datang satu per satu. Bisakah kamu melaporkan median dari semua nilai yang telah dilihat sejauh ini setelah setiap nilai datang, dalam waktu O(log n) per nilai?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kamu hanya membutuhkan satu posisi dalam urutan terurut, bukan semuanya n. Min-heap berukuran k hanya menyimpan nilai yang masih bisa menjadi jawaban, sedangkan quickselect membagi data seperti quicksort, tetapi hanya mengikuti sisi yang memuat jawaban. Dengan begitu, waktu rata-ratanya turun menjadi O(n).

Urutkan dan baca satu posisi

Intuisi

Nilai terbesar ke-k ditentukan berdasarkan urutan yang sudah diurutkan, jadi urutkan lalu baca satu posisi: indeks k-1 pada urutan dari terbesar ke terkecil, atau indeks n-k pada urutan dari terkecil ke terbesar. Jika diurutkan dari terbesar ke terkecil, contoh pertama adalah [9, 9, 7, 4, 2, 1], dan indeks 1 berisi 9 yang kedua. Setiap kemunculan nilai mempertahankan posisinya sendiri.

Dengan n = 10^4, pengurutan membutuhkan sekitar 1.3 × 10^5 perbandingan, untuk mengurutkan semua n nilai saat hanya satu posisi yang penting.

Algoritma

Salin nums agar array milik pemanggil tetap seperti semula.
Urutkan salinannya. Gunakan perbandingan numerik, beberapa bahasa secara default membandingkan angka sebagai teks.
Kembalikan indeks k-1 dalam urutan dari terbesar ke terkecil, atau indeks n-k dalam urutan dari terkecil ke terbesar.

def findKthLargest(nums, k):
    # Largest first: the k-th largest sits at index k-1.
    ordered = sorted(nums, reverse=True)
    return ordered[k - 1]

Simpan k elemen terbesar dalam min-heap

Intuisi

Nilai terbesar ke-k adalah yang terkecil di antara k nilai terbesar. Jadi, telusuri nums satu kali dan simpan k nilai terbesar yang ditemukan sejauh ini dalam min-heap, yang elemen teratasnya adalah nilai terkecil tersebut.

Setelah heap berisi k nilai, bandingkan setiap x baru dengan elemen teratas. Jika x tidak lebih besar, ada k nilai yang disimpan dan setidaknya sama besar, jadi x tidak mungkin menjadi jawabannya. Jika lebih besar, elemen teratas keluar dari k nilai terbesar dan digantikan oleh x. Pada contoh 2 dengan k = 4, elemen teratas setelah empat nilai pertama adalah -3; 2 menggantikannya, dan elemen teratas yang baru, 0, adalah jawabannya.

Setiap nilai membutuhkan paling banyak satu langkah heap O(log k): waktu O(n log k) dan memori O(k).

Algoritma

Mulai dengan min-heap kosong.
Untuk setiap nilai x, tambahkan selama heap menyimpan kurang dari k nilai.
Setelah heap menyimpan k nilai, ganti nilai teratas dengan x hanya jika x lebih besar daripada nilai teratas.
Setelah nilai terakhir, kembalikan nilai teratas heap.

import heapq


def findKthLargest(nums, k):
    # A min-heap of the k largest values so far; its top is the smallest of them.
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x
    return heap[0]

Quickselect dengan partisi tiga arah

Intuisi

Setelah satu partisi quicksort, pivot berada di indeks akhir dalam urutan terurut, meskipun kedua sisinya belum terurut. Dalam urutan dari yang terkecil, jawaban berada di target = n-k, jadi setelah setiap partisi, kamu hanya melanjutkan di sisi yang memuat target.

Pada contoh pertama, target adalah 4. Mempartisi di sekitar 4 menempatkan 7, 9, 9 pada indeks 3 hingga 5, jadi kamu mempertahankan sisi itu. Mempartisinya di sekitar 9 menempatkan kedua angka 9 pada indeks 4 dan 5, dan indeks 4 memuat jawabannya.

Partisi tiga arah mengelompokkan nilai yang sama dengan pivot di dalam [lt, gt], yang sudah berada di posisi terurut, sehingga pencarian berakhir jika target berada di dalamnya. Pivot acak jatuh di paruh tengah dalam separuh kesempatan, sehingga rentang menyusut hingga paling banyak tiga perempat, jadi perkiraan kerjanya adalah O(n); kasus terburuknya tetap O(n²). Mempartisi salinan memerlukan memori O(n).

Algoritma

Salin nums ke a, tetapkan target = n-k, lo = 0 dan hi = n-1.
Pilih pivot acak dari a[lo..hi].
Bagi a[lo..hi] menjadi nilai yang lebih kecil dari, sama dengan, dan lebih besar dari pivot, dengan membiarkan nilai-nilai yang sama berada di a[lt..gt].
Jika target < lt, tetapkan hi = lt-1; jika target > gt, tetapkan lo = gt+1; jika tidak, kembalikan pivot.
Ulangi mulai dari langkah 2.

import random


def findKthLargest(nums, k):
    a = list(nums)
    target = len(a) - k  # the answer's index once a is sorted smallest first
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # Now a[lt..gt] all equal pivot, and they are in their sorted places.
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot

Jebakan dan kasus tepi

Menghapus duplikat terlebih dahulu. Pada contoh pertama, jawabannya adalah 9, tetapi setelah array diubah menjadi set, hasilnya menjadi 7.
Membaca indeks n-k-1. k dihitung mulai dari 1, jadi jawabannya berada di posisi n-k dalam urutan dari yang terkecil.
Mengurutkan angka sebagai teks. Dalam JavaScript dan TypeScript, [10, 9, 2].sort() menghasilkan [10, 2, 9]; berikan (a, b) => a - b.
Menggunakan max-heap berukuran k. Mengeluarkan nilai terbesar akan mempertahankan k nilai terkecil dan menghasilkan nilai terkecil ke-k.
Menggunakan Quickselect dengan partisi dua arah atau pivot tetap. 10^4 salinan 7, atau array yang sudah terurut, mengurangi rentang sebanyak satu nilai per putaran: sekitar 5 × 10^7 langkah.

Pertanyaan yang sering diajukan4

Berapa kompleksitas waktu untuk Elemen Terbesar ke-K dalam sebuah Array?

Pengurutan membutuhkan waktu O(n log n). Min-heap berukuran k membutuhkan waktu O(n log k) dan memori O(k). Quickselect dengan pivot acak membutuhkan waktu O(n) secara rata-rata dan O(n²) pada kasus terburuk, yang sangat kecil kemungkinannya terjadi dengan pivot acak.

Mengapa menggunakan min-heap, bukan max-heap, untuk menemukan elemen terbesar ke-k?

Nilai yang kamu bandingkan dan keluarkan adalah yang terkecil dari k nilai terbesar, jadi nilai itu harus berada di posisi teratas. max-heap hanya berfungsi jika kamu memasukkan semua n nilai ke dalamnya dan melakukan pop sebanyak k-1 kali, yang membutuhkan memori O(n).

Haruskah saya menggunakan heap atau quickselect untuk menemukan elemen terbesar ke-k?

Quickselect lebih cepat secara rata-rata, O(n), tetapi membutuhkan semua nilai di memori dan mengurutkannya ulang. Heap memiliki kompleksitas O(n log k) tanpa kasus terburuk yang buruk, dan dapat digunakan saat nilai tiba satu per satu.

Apakah elemen terbesar ke-k dapat ditemukan dalam waktu linear pada kasus terburuk?

Ya. Aturan median dari median memilih pivot yang dijamin memangkas bagian tetap dari nilai, sehingga pemilihan berjalan dalam O(n) pada kasus terburuk, meskipun lebih lambat dalam praktiknya. Dengan nilai dari -10^4 hingga 10^4, menghitung setiap nilai juga dapat dilakukan dalam waktu linear.

def findKthLargest(nums, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [7, 2, 9, 4, 9, 1]
k = 2

Output yang diharapkan

Kth Largest Element in an Array

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Urutkan dan baca satu posisi

Simpan k elemen terbesar dalam min-heap

Quickselect dengan partisi tiga arah

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan4

Soal serupa