KTH配列内の最大要素

11989 ワード
leetcode algorithms heap array テキストリンク
leetcode問題を参照できます215. Kth Largest Element in an Array

問題声明


整数配列nums と整数k , リターンkth 配列の最大要素.

Note that it is the kth largest element in the sorted order, not the kth distinct element.


例


Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

アプローチ1：ソートの使用


ソートを使用してNums配列を自然順でソートし、最初から最後のI . E - N - K要素からKth要素を返します.

K index from end is equal to length-k index from start


class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

複雑性解析


TCO(N log N) , どこN は入力配列のサイズです
SCO(1)

アプローチ2：ヒープの使用


実際には、我々が使用を選択した場合、複数のサブアプローチがありますHeap .
アプローチ
元素数
投票数
サイズNの最小ヒープ
min heapすべての要素を格納するN-K 任意の時間の最小要素
世論調査N-K 時代kth 最大
ヒープオブサイズ
min heap最もk個の要素を格納する.最初のk要素が追加された後に新しい要素を追加すると、新しい要素がヒープルート(Peek)より大きいかどうかを確認します
1回のポーリングを行い、polled要素を返す
サイズの最大ヒープ
すべてのn要素を格納する最大ヒープK 任意の時間の最大要素
世論調査K 時代kth 最大

サイズNの最小ヒープ
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue();

        for(int num: nums){
            minHeap.offer(num);
        }

        int i = 0;
        int kThLargest = minHeap.poll();

        while (i++ < (n - k)) {
            kThLargest = minHeap.poll();
        }

        return kThLargest;
    }
}

ヒープオブサイズ
import java.util.Arrays;
import java.util.Collections;

//Min Heap of size K
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;

        if (n == 1) {
            return nums[0];
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue(k);

        for(int i=0; i<k; i++){
            minHeap.offer(nums[i]);
        }

        for(int i=k; i<n; i++){
            if(minHeap.peek() < nums[i]){
                minHeap.poll();
                minHeap.offer(nums[i]);    
            }
        }

        return minHeap.poll();
    }
}

サイズの最大ヒープ
class Solution {
    public int findKthLargest(int[] nums, int k) {

        int len = nums.length;

        if(len == 1){
            return nums[0];
        }

        // Since we are using Max-Heap, we need to sort accordingly
        Comparator<Integer> comp = (a,b) -> b.compareTo(a);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(comp);

        // Add all the elements
        for(int num: nums){
            maxHeap.offer(num);
        }

        // we need to poll for k-1 times and
        // return the next polled element
        int i = 1;

        while(i++ < k){
            maxHeap.poll();
        }

        return  maxHeap.poll();

    }
}
問題信用leetcode.com
[オペレーティングシステム]モニタ
🌈 CSS Selector