Rumah> Java> javaTutorial> teks badan

Bagaimana untuk menyelesaikan masalah Top-K menggunakan Java

PHPz
Lepaskan: 2023-04-22 15:04:08
ke hadapan
1301 orang telah melayarinya

Tajuk

Cari nombor K terkecil

Reka bentuk algoritma untuk mencari nombor k terkecil dalam tatasusunan. Nombor k ini boleh dikembalikan dalam sebarang susunan.

Bagaimana untuk menyelesaikan masalah Top-K menggunakan Java

Penyelesaian masalah

Kaedah 1

Isih (gelembung/pilih)

Idea

1. Bubble sorting menentukan kedudukan akhir setiap kali ia dilaksanakan Selepas melaksanakan K kali, keputusan boleh diperolehi Kerumitan masa ialah O(n * k, Apabila k

2. Setiap kali pengisihan pemilihan dilaksanakan, nombor terbesar atau terkecil akan ditentukan dan diletakkan di satu hujung Melalui pengisihan pilihan, nombor K maksimum boleh diperolehi dengan melaksanakan K kali. Kerumitan masa ialah O(N * K).

Pelaksanaan Kod

//冒泡排序 public static int[] topKByBubble(int[] arr, int k) { int[] ret = new int[k]; if (k == 0 || arr.length == 0) { return ret; } for (int i = 0; i < k; i++) { for (int j = arr.length - 1; j < i; j--) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } ret[i] = arr[i]; } return ret; } //选择排序 public static int[] topKBySelect(int[] arr, int k) { int[] ret = new int[k]; for (int i = 0; i < k; i++) { int maxIndex = i; int maxNum = arr[maxIndex]; for (int j = i + 1; j < arr.length; j++) { if (arr[j] > maxNum) { maxIndex = j; maxNum = arr[j]; } } if (maxIndex != i) { swap(arr, maxIndex, i); } ret[i] = arr[i]; } return ret; } public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
Salin selepas log masuk

Kaedah 2

Bahagi dan Takluk-Isih Cepat

Idea

1 sort ialah Idea bahagi dan takluk, mula-mula bahagikan urutan kepada dua bahagian melalui bahagi dan takluk partition, dan kemudian ulangi dua bahagian itu lagi; iaitu, bahagikan partition operasi, dan laraskan urutan mengikut pangsi elemen utama , yang lebih besar daripada pangsi diletakkan di hujung kiri, dan yang lebih kecil daripada pangsi diletakkan di hujung kanan Ini menentukan kedudukan daripada pivot elemen utama, pivotIndex Jika pivotIndex adalah k-1, maka nombor dalam kedudukan k-1 pertama ialah elemen k-terbesar, iaitu K atas yang kami perlukan.

Kerumitan masa: O(n)

Pelaksanaan kod

Kaedah 3
public static int[] topKByPartition(int[] arr, int k){ if(arr.length == 0 || k <= 0){ return new int[0]; } return quickSort(arr,0,arr.length-1,k); } //快速排序 public static int[] quickSort(int[] arr, int low, int high, int k){ int n = arr.length; int pivotIndex = partition(arr, low, high); if(pivotIndex == k-1){ return Arrays.copyOfRange(arr,0,k); }else if(pivotIndex > k-1){ return quickSort(arr,low,pivotIndex-1,k); }else { return quickSort(arr,pivotIndex+1,high,k); } } public static int partition(int[] arr, int low, int high){ if(high - low == 0){ return low; } int pivot = arr[high]; int left = low; int right = high-1; while (left < right){ while (left < right && arr[left] > pivot){ left++; } while (left < right && arr[right] < pivot){ right--; } if(left < right){ swap(arr,left,right); }else { break; } } swap(arr,high,left); return left; } public static void swap(int[] arr,int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
Salin selepas log masuk

Menggunakan timbunan

Idea

1, bina timbunan maksimum

2, lintasi tatasusunan asal, dan letakkan elemen ke dalam baris gilir Apabila saiz timbunan ialah K, anda hanya perlu membandingkan elemen teratas bagi timbunan dengan elemen seterusnya Jika ia lebih besar daripada bahagian atas unsur timbunan, padamkan elemen atas timbunan dan masukkan unsur tersebut ke dalam timbunan sehingga semua elemen dilalui

3, dan nombor K disimpan dalam baris gilir ditangguhkan

Kerumitan masa: O (N*logK)

Pelaksanaan kod

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah Top-K menggunakan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan:
sumber:yisu.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!