整数配列前Kが大きい問題

このような問題は最高周波K項の基礎問題である.質問の説明は次のとおりです: ， k オフラインアルゴリズム
このオフライン処理では,Quick Selectアルゴリズムを用いることができる.O(N)時間以内に配列のK番目の大きな数を見つけ、配列全体をスキャンすると前のK番目の大きな数が得られる.このアルゴリズムは速排思想に基づいている.
Quick Select
Quick Selectアルゴリズムの基本思想:

速列の分治思想を利用して、探索対象配列の主元pivotを求め、主元を境に左右2つの区間

に分ける.

主元の位置を比較することにより、K番目の大きさの数が主元左区間か主元右区間かを判断する.それとも主元ですか?(境界条件の判断にも注意し、境界にある可能性がある)

サブゾーン間再帰呼び出し

import java.util.Random;

class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        // Write your code here
        quickSort(nums, 0, nums.length - 1, k);

        int[] topk = new int[k];
        for (int i = 0; i < k; ++i)
            topk[i] = nums[i];

        return topk;
    }
    
    private void quickSort(int[] A, int start, int end, int k) {
        if (start >= k)
            return;

        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        //          
        Random rand =new Random(end - start + 1);
        //nextInt(int n)             int ，    [0,n)   ，   0 n     int ，  0    n
        int index = rand.nextInt(end - start + 1) + start;
        int pivot = A[index];

        // key point 2: every time you compare left & right, it should be 
        // left <= right not left < right
        while (left <= right) {
            // key point 3: A[left] < pivot not A[left] <= pivot
            while (left <= right && A[left] > pivot) {
                left++;
            }
            // key point 3: A[right] > pivot not A[right] >= pivot
            while (left <= right && A[right] < pivot) {
                right--;
            }

            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left++;
                right--;
            }
        }
        
        quickSort(A, start, right, k);
        quickSort(A, left, end, k);
    }
}

オンラインアルゴリズム
データ・ストリームの形式では、最初から遍歴する機会はありません.解決策は山を考えることだ.この問題では、削除操作をサポートする必要はありません.データは増加しても減らないだけです.では、K位にランクインしたデータは、前のk位に入る機会がありません.そのため、これらのデータを保持する意味は大きくありません.削除することができます.これで、最小のスタックを維持する必要があります.整数がTopKの集合に加わるかどうかを決定する必要がある場合、決定的な要因は、現在の整数がTopKの最小数よりも大きいかどうかである.したがって,TopKのk個の整数では,最小のスタックを維持し,最小の整数を推挙してデータストリームから新しく出た整数と比較し,新しく来た数がもっと大きいと,スタック内の最小の整数を蹴り落とし,新しい数を加え,逆に新しい数を捨てるべきである.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (k <= 0 || nums.length == 0 || nums == null) {
            return 0;
        }
        PriorityQueue minHeap = new PriorityQueue();
        for (int i = 0; i < nums.length; i++) {
            minHeap.add(nums[i]);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.poll();
    }
}

高速ソートの実装

# quicksort

class Solution:

    def quicksort(self, A, start, end):

        if A is None or len(A) == 0:
            return None

        if start >= end:
            return None

        left = start
        right = end
        # pivot is value not index
        pivot = start + (end - start) // 2

        #    left <= right，  stackoverflow
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            while left <= right and A[right] > pivot:
                right -= 1
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1

        self.quicksort(A, start, right)
        self.quicksort(A, left, end)

集計ソートの実装

class Solution:

    def sortIntegers(self, A):
        
        temp = [0 for _ in range len(A)]
        self.merge_sert(0, len(A) - 1, A, temp)

    def merge_sort(self, start, end, A, temp):

        if start >= end:
            return 

        mid = start + (end - start) // 2
        self.merge_sort(start, mid, A, temp)
        self.merge_sort(mid+1, end, A, temp)
        self.merge(start, mid, end, A, temp)

    def merge(self, start, mid, A, end, temp):
        left = start
        right = mid + 1
        index = start
        while left <= mid and right <= end:
            if A[left] < A[right]:
                temp[index] = A[left]
                left += 1
            else:
                temp[index] = A[right]
                right += 1

            index += 1

        while left <= mid:
            temp[index] = A[left]
            left += 1

        while right <= end:
            temp[index] = A[right]
            right += 1

        for index in range(start, end+1):
            A[index] = temp[index]