So lösen Sie Top-K-Probleme mit Java

Frage

Finden Sie die kleinste K-Zahl

Entwerfen Sie einen Algorithmus, um die kleinste K-Zahl im Array zu finden. Diese k Zahlen können in beliebiger Reihenfolge zurückgegeben werden.

Problemlösung

Methode 1

Sortieren (Blase/Auswahl)

Idee

1. Die Blasensortierung besteht darin, bei jeder Ausführung K-mal die endgültige Position zu ermitteln , die Zeitkomplexität ist O(n * k). Wenn k

2. Bei jeder Auswahlsortierung wird die größte oder kleinste Zahl ermittelt und an einem Ende platziert. Durch die Auswahlsortierung kann die maximale K-Zahl ermittelt werden. Die Zeitkomplexität beträgt O(N * K).

Code-Implementierung

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

Methode 2

Divide and Conquer-Quick Sort

Idee

1. Der Kern der Quick Sort ist die Idee von „Divide and Conquer“. Teilen Sie zunächst die Sequenz durch „Divide and Conquer“ in zwei Teile Erobern Sie die Partition und teilen Sie sie dann erneut.

2 Verwenden Sie die Idee des Teilens und Eroberns, d am linken Ende und der kleinere als der Pivot am rechten Ende, wodurch die Position des Hauptelements Pivot, PivotIndex, bestimmt wird. Wenn PivotIndex zufällig k-1 ist, dann ist die Zahl an der ersten k-1-Position die oberste k größtes Element, das das oberste K ist, das wir benötigen. Zeitkomplexität: O(n) der Heap Wenn es K ist, müssen Sie nur das oberste Element des Heaps mit dem nächsten Element vergleichen. Wenn es größer als das oberste Element des Heaps ist, löschen Sie das oberste Element des Heaps und fügen Sie das Element in den Heap ein Alle Elemente werden durchlaufen

3, und die in der Warteschlange gespeicherten K sind Anzahl der aus der Warteschlange entfernten Elemente

Zeitliche Komplexität: O(N*logK)

Code-Implementierung

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

Das obige ist der detaillierte Inhalt vonSo lösen Sie Top-K-Probleme mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!