Java を使用して Top-K 問題を解く方法

質問

最小の K 数を見つける

配列内の最小の K 数を見つけるアルゴリズムを設計します。これらの k 個の数値は、任意の順序で返すことができます。

#問題の解決策

方法 1

並べ替え (バブル/選択)

アイデア

1. バブルソートは実行するたびに最終位置を決定します。K回実行すると結果が得られます。時間計算量はO(n * k)です。k2. 選択ソートは実行するたびに最大値または最小値を決定して端に配置するため、K 回実行することで最大 K 個の値が得られます。時間計算量は O(N * K) です。

コードの実装

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

方法 2

分割統治 - クイック ソート

アイデア

1、クイック ソートの核心は次のとおりです。分割統治 このアイデアは、最初に分割統治によってシーケンスを 2 つの部分に分割し、次にその 2 つの部分を再度再帰することです。

2、分割統治の概念を使用します。つまり、操作パーティションを分割します。 , メイン要素のピボットに従ってシーケンスを調整し、比較します。大きいピボットは左端に配置され、小さいピボットは右端に配置されます。これにより、メイン要素のピボットの pivotIndex が決定されます。pivotIndex が k- である場合は、 1 の場合、最初の k-1 位置の数値は上位 k 個の最大要素です。つまり、上位 K 個が必要です。

時間計算量: O(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;
}

方法 3

ヒープの使用

アイデア

1, 最大のヒープを構築します

##2, 元の配列を走査し、要素をキューに入れます。ヒープのサイズが K の場合、ヒープの先頭の要素と比較するだけで済みます。次の要素。それがヒープの最上位の要素より大きい場合は、ヒープの最上位の要素を削除し、すべての要素が走査されるまでその要素をヒープに挿入します。

3、および K 番号キューに格納されたデータはデキューされます

時間計算量: O(N *logK)

コード実装

public class TopK {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(k==0 || arr.length==0){
            return ret;
        }
        // 1,构建一个最大堆
        // JDK的优先级队列是最小堆， 就要用到我们比较器
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //2,遍历原数组，进行入队
        for(int value:arr){
            if(queue.size() < k){
                queue.offer(value);
            }else{
                if(value < queue.peek()){
                    queue.poll();
                    queue.offer(value);
                }
            }
        }
        //3,将queue中存储的K个元素出队
        for(int i = 0;i < k;i++){
            ret[i] = queue.poll();
        }
        return ret;
    }
}

以上がJava を使用して Top-K 問題を解く方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。