Comment résoudre les problèmes Top-K en utilisant Java

Question

Trouver le plus petit nombre K

Concevez un algorithme pour trouver le plus petit nombre k du tableau. Ces k nombres peuvent être renvoyés dans n’importe quel ordre.

Solution du problème

Méthode 1

Tri (bulle/sélection)

Idée

1. Le tri des bulles consiste à déterminer la position finale à chaque fois qu'il est exécuté. Après K fois, vous pouvez obtenir le résultat. , la complexité temporelle est O(n * k). Lorsque k

2. Chaque fois que le tri par sélection est exécuté, le nombre le plus grand ou le plus petit sera déterminé et placé à une extrémité. Grâce au tri par sélection, le nombre K maximum peut être obtenu en exécutant K fois. La complexité temporelle est O(N * K).

Implémentation du code

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

Méthode 2

Diviser et conquérir-Tri rapide

Idée

1. Le cœur du tri rapide est l'idée de diviser pour régner. Tout d'abord, divisez la séquence en deux parties en diviser et régner. conquérir la partition, puis diviser à nouveau les deux parties ;

2, utiliser l'idée de diviser pour régner, c'est-à-dire diviser la partition d'opération, ajuster la séquence en fonction du pivot de l'élément principal, mettre celle plus grande que le pivot. l'extrémité gauche, et le plus petit que le pivot à l'extrémité droite, déterminez ainsi la position du pivot de l'élément principal, pivotIndex. Si pivotIndex se trouve être k-1, alors le nombre dans la première position k-1 est le haut k le plus grand élément, qui est le K supérieur dont nous avons besoin.

Complexité temporelle : O(n)

Implémentation du code

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

Troisième méthode

Utilisez le tas

Idée

1, construisez un tas maximum

2, parcourez le tableau d'origine, mettez les éléments en file d'attente, lorsque la taille de le tas Lorsqu'il est K, il vous suffit de comparer l'élément supérieur du tas avec l'élément suivant. S'il est supérieur à l'élément supérieur du tas, supprimez l'élément supérieur du tas et insérez l'élément dans le tas jusqu'à ce que. tous les éléments sont parcourus

3, et le K stocké dans la file d'attente est Nombre d'éléments retirés de la file d'attente

Complexité temporelle : O(N*logK)

Implémentation du code

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!