Bagaimana untuk menyelesaikan masalah Top-K menggunakan Java

Tajuk

Cari nombor K terkecil

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

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;
    }

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;
}

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!