Java怎么解決Top-K的問題

這篇文章主要介紹“Java怎么解決Top-K的問題”，在日常操作中，相信很多人在Java怎么解決Top-K的問題問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java怎么解決Top-K的問題”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

題目

求最小的K個(gè)數(shù)

設(shè)計(jì)一個(gè)算法，找出數(shù)組中最小的k個(gè)數(shù)。以任意順序返回這k個(gè)數(shù)均可。

解題方案

方法一

排序（冒泡/選擇）

思路

1，冒泡排序是每執(zhí)行一次，就會(huì)確定最終位置，執(zhí)行K次后，就可以得到結(jié)果，時(shí)間復(fù)雜度為O(n * k),當(dāng)k<<n時(shí)，O(n * k)的性能會(huì)比O(N*logN)好。

2，選擇排序每執(zhí)行依次，就會(huì)通過確定一個(gè)最大的或最小的放在一端，通過選擇排序，執(zhí)行K次就可以得到最大的K個(gè)數(shù)了。時(shí)間復(fù)雜度時(shí)O(N * K)。

代碼實(shí)現(xiàn)

  //冒泡排序
    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;
    }

方法二

分治-快速排序

思路

1，快速排序的核心是分治思想，先通過分治partition把序列分為兩個(gè)部分，再將兩個(gè)部分進(jìn)行再次遞歸；

2,利用分治思想，即劃分操作partition，根據(jù)主元素pivot調(diào)整序列，比pivot大的放在左端，比pivot小的放在右端，這樣確定主元素pivot的位置pivotIndex，如果pivotIndex剛好是k-1，那么前k-1位置的數(shù)就是前k大的元素，即我們要求的top K。

時(shí)間復(fù)雜度: O(n)

代碼實(shí)現(xiàn)

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

方法三

利用堆

思路

1，構(gòu)建一個(gè)最大堆

2，遍歷原數(shù)組，元素入隊(duì)，當(dāng)堆的大小為K時(shí)，只需要將堆頂元素于下一個(gè)元素比較，如果大于堆頂元素，則將堆頂元素刪除，將該元素插入堆中，直到遍歷完所有元素

3，將queue存儲(chǔ)的K個(gè)數(shù)出隊(duì)

時(shí)間復(fù)雜度：為O(N*logK)

代碼實(shí)現(xiàn)

public class TopK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k==0 || arr.length==0){
            return ret;
        }
        // 1,構(gòu)建一個(gè)最大堆
        // JDK的優(yōu)先級(jí)隊(duì)列是最小堆， 就要用到我們比較器
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2,遍歷原數(shù)組，進(jìn)行入隊(duì)
        for(int value:arr){
            if(queue.size() < k){
                queue.offer(value);
            }else{
                if(value < queue.peek()){
                    queue.poll();
                    queue.offer(value);
                }
            }
        }
        //3,將queue中存儲(chǔ)的K個(gè)元素出隊(duì)
        for(int i = 0;i < k;i++){
            ret[i] = queue.poll();
        }
        return ret;
    }
}

到此，關(guān)于“Java怎么解決Top-K的問題”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！