Cara Menemukan Unsur Terbesar Kth di Jawa

1. Perkenalan

Pada artikel ini, kami akan menyajikan berbagai solusi untuk mencari elemen terbesar ke- k dalam deretan angka unik. Kami akan menggunakan array bilangan bulat untuk contoh kami.

Kami juga akan berbicara tentang kompleksitas waktu rata-rata dan kasus terburuk setiap algoritme.

2. Solusi

Sekarang mari kita jelajahi beberapa solusi yang mungkin - satu menggunakan tipe biasa, dan dua menggunakan algoritma Quick Select yang diturunkan dari Quick Sort.

2.1. Penyortiran

Ketika kita memikirkan masalahnya, mungkin solusi paling jelas yang muncul di benak kita adalah mengurutkan array .

Mari tentukan langkah-langkah yang diperlukan:

  • Urutkan larik dalam urutan menaik
  • Sebagai elemen terakhir dari array akan menjadi elemen terbesar, k th elemen terbesar akan berada di xth indeks, di mana x = panjang (array) - k

Seperti yang bisa kita lihat, solusinya sangat mudah tetapi membutuhkan penyortiran seluruh larik. Karenanya, kompleksitas waktu akan menjadi O (n * logn) :

public int findKthLargestBySorting(Integer[] arr, int k) { Arrays.sort(arr); int targetIndex = arr.length - k; return arr[targetIndex]; }

Pendekatan alternatif adalah dengan mengurutkan array dalam urutan menurun dan hanya mengembalikan elemen pada indeks (k-1) :

public int findKthLargestBySortingDesc(Integer[] arr, int k) { Arrays.sort(arr, Collections.reverseOrder()); return arr[k-1]; }

2.2. QuickSelect

Ini dapat dianggap sebagai pengoptimalan dari pendekatan sebelumnya. Dalam hal ini, kami memilih QuickSort untuk penyortiran. Menganalisis pernyataan masalah, kita menyadari bahwa kita sebenarnya tidak perlu mengurutkan seluruh array - kita hanya perlu mengatur ulang isinya sehingga elemen ke- k dari array tersebut adalah yang terbesar atau terkecil ke- k .

Di QuickSort, kami memilih elemen pivot dan memindahkannya ke posisi yang benar. Kami juga mempartisi array di sekitarnya. Dalam QuickSelect, idenya adalah untuk berhenti di titik di mana pivot itu sendiri adalah elemen terbesar ke- k .

Kita dapat mengoptimalkan algoritme lebih jauh jika tidak berulang untuk sisi kiri dan kanan pivot. Kita hanya perlu mengulang untuk salah satunya sesuai dengan posisi porosnya.

Mari kita lihat ide dasar dari algoritma QuickSelect:

  • Pilih elemen pivot dan partisi array yang sesuai
    • Pilih elemen paling kanan sebagai poros
    • Susun ulang larik sedemikian rupa sehingga elemen pivot ditempatkan di tempat yang semestinya - semua elemen yang kurang dari pivot akan berada di indeks yang lebih rendah, dan elemen yang lebih besar dari pivot akan ditempatkan di indeks yang lebih tinggi daripada pivot
  • Jika pivot ditempatkan pada elemen k dalam larik, keluar dari proses, karena pivot adalah elemen terbesar ke k
  • Jika posisi pivot lebih besar dari k, lanjutkan proses dengan subarray kiri, jika tidak, ulangi proses dengan subarray kanan

Kita dapat menulis logika generik yang dapat digunakan untuk mencari elemen terkecil ke k juga. Kami akan mendefinisikan sebuah metode findKthElementByQuickSelect () yang akan mengembalikan k elemen th di array diurutkan.

Jika kita mengurutkan array dalam urutan menaik, elemen ke- k dari sebuah array akan menjadi elemen terkecil ke- k . Untuk mencari elemen terbesar ke- k , kita dapat melewatkan k = length (Array) - k.

Mari terapkan solusi ini:

public int findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) { if (k >= 0 && k  k) { return findKthElementByQuickSelect(arr, left, pos - 1, k); } return findKthElementByQuickSelect(arr, pos + 1, right, k - pos + left - 1); } return 0; }

Sekarang mari kita terapkan metode partisi , yang mengambil elemen paling kanan sebagai pivot, meletakkannya di indeks yang sesuai, dan mempartisi larik sedemikian rupa sehingga elemen pada indeks yang lebih rendah harus lebih kecil dari elemen pivot.

Demikian pula, elemen pada indeks yang lebih tinggi akan lebih besar dari elemen pivot:

public int partition(Integer[] arr, int left, int right) { int pivot = arr[right]; Integer[] leftArr; Integer[] rightArr; leftArr = IntStream.range(left, right) .filter(i -> arr[i]  arr[i]) .boxed() .toArray(Integer[]::new); rightArr = IntStream.range(left, right) .filter(i -> arr[i] > pivot) .map(i -> arr[i]) .boxed() .toArray(Integer[]::new); int leftArraySize = leftArr.length; System.arraycopy(leftArr, 0, arr, left, leftArraySize); arr[leftArraySize+left] = pivot; System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); return left + leftArraySize; }

Ada pendekatan yang lebih sederhana dan berulang untuk mencapai partisi:

public int partitionIterative(Integer[] arr, int left, int right) { int pivot = arr[right], i = left; for (int j = left; j <= right - 1; j++) { if (arr[j] <= pivot) { swap(arr, i, j); i++; } } swap(arr, i, right); return i; } public void swap(Integer[] arr, int n1, int n2) { int temp = arr[n2]; arr[n2] = arr[n1]; arr[n1] = temp; }

Solusi ini bekerja rata-rata dalam waktu O (n) . Namun, dalam kasus terburuk, kompleksitas waktu akan menjadi O (n ^ 2) .

2.3. QuickSelect Dengan Partisi Acak

Pendekatan ini merupakan sedikit modifikasi dari pendekatan sebelumnya. Jika array hampir / seluruhnya diurutkan dan jika kita memilih elemen paling kanan sebagai pivot, partisi subarray kiri dan kanan akan sangat tidak rata.

Metode ini menyarankan untuk memilih elemen pivot awal secara acak. Kami tidak perlu mengubah logika partisi.

Alih-alih memanggil partisi , kami memanggil metode randomPartition , yang mengambil elemen acak dan menukar dengan elemen paling kanan sebelum akhirnya menjalankan metode partisi .

Mari terapkan metode randomPartition :

public int randomPartition(Integer arr[], int left, int right) { int n = right - left + 1; int pivot = (int) (Math.random()) * n; swap(arr, left + pivot, right); return partition(arr, left, right); }

Solusi ini bekerja lebih baik daripada kasus sebelumnya dalam banyak kasus.

Kompleksitas waktu yang diharapkan dari QuickSelect yang diacak adalah O (n) .

Namun, kompleksitas waktu terburuk masih tetap O (n ^ 2) .

3. Kesimpulan

Pada artikel ini, kita membahas solusi berbeda untuk mencari elemen terbesar (atau terkecil) ke k dalam deretan bilangan unik. Solusi paling sederhana adalah mengurutkan array dan mengembalikan elemen ke k . Solusi ini memiliki kompleksitas waktu O (n * logn) .

Kami juga membahas dua variasi Quick Select. Algoritme ini tidak langsung tetapi memiliki kompleksitas waktu O (n) dalam kasus rata-rata.

Seperti biasa, kode lengkap untuk algoritme dapat ditemukan di GitHub.