스트림 Leetcode 솔루션에서 K 번째로 큰 요소


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 상자 이베이 페이스북 서비스 골드만 삭스 구글 Microsoft 뉴타 닉스
암호알고리즘 디자인 더미

문제 정책

이 문제에서 우리는 클래스를 디자인해야합니다. KthLargest () 처음에는 정수 k와 정렬 정수 정수 k와 배열이있을 때 매개 변수화 된 생성자를 작성해야합니다. nums 인수로 전달됩니다. 클래스에는 또한 기능이 있습니다 추가 (발) 가치가있는 새로운 요소를 추가하는 파 정수 스트림으로. 각각 더하다() 호출하면 실행중인 스트림에서 K 번째로 큰 요소 인 정수를 반환해야합니다.

["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
4 5 5 8 8

설명 :

스트림 Leetcode 솔루션에서 K 번째로 큰 요소

접근 (최소 힙)

K 번째 가장 작은 / 가장 큰 요소를 찾을 때마다 거의 매번 최대 / 최소 힙이 목적에 부합합니다. 이는 요소를 정렬 된 (우선 순위가 지정된) 방식으로 유지하는 유연한 특성 때문입니다. 여기에서 쿼리가 생성 될 때마다 요소를 포함하기 위해 배열을 사용할 수도 있습니다. 그러나 찾기 위해서는 배열에서 K 번째로 큰 요소, 우리는 각 쿼리에 대해 O (N) 시간을 사용해야합니다. 따라서 O (1) 시간에서 k 번째로 큰 요소를 찾기 위해 크기 k의 최소 힙을 유지할 수 있습니다. 최소 힙을 사용하고 있으므로 최상위 요소는 힙에서 가장 작습니다. 그리고 우리는 모든 쿼리 후에 힙 크기를 k와 같도록 바인딩했기 때문에이 최상위 요소는 전체 스트림에서 K 번째로 큰 요소가됩니다 (힙은 k 개의 가장 큰 요소 만 유지하므로).

스트림 Leetcode 솔루션에서 K 번째로 큰 요소 구현

C ++ 프로그램

#include <bits/stdc++.h>

using namespace std;

class KthLargest {
public:
    priority_queue <int , vector <int> , greater <int> > pq;
    int K;

    KthLargest(int k, vector<int>& nums) {
        K = k;
        for(int &x : nums) {
            pq.push(x);
            if(pq.size() > k) {
                pq.pop();
            }
        }
    }

    int add(int val) {
        pq.push(val);
        if(pq.size() > K)
            pq.pop();
        return pq.top();
    }
};

int main() {
    vector <int> nums = {4 , 5 , 8 , 2};
    int k = 3;
    KthLargest stream(k , nums);
    cout << stream.add(3) << " ";
    cout << stream.add(5) << " ";
    cout << stream.add(10) << " ";
    cout << stream.add(9) << " ";
    cout << stream.add(4) << " ";
    cout << endl;
    return 0;
}

자바 프로그램

import java.util.*;
import java.io.*;

class comp implements Comparator<Integer> {
    public int compare(Integer a , Integer b) {
        if(a > b)
            return 1;
        if(a < b)
            return -1;
        return 0;
    }
}

class KthLargest {
    int K;
    PriorityQueue <Integer> pq;

    public KthLargest(int k, int[] nums) {
        K = k;
        pq = new PriorityQueue <Integer> (new comp());
        for(int x : nums) {
            pq.add(x);
            if(pq.size() > k) {
                pq.remove();
            }
        }
    }

    int add(int val) {
        pq.add(val);
        if(pq.size() > K)
            pq.remove();
        return pq.peek();
    }
}

class KthLargestInStream {
    public static void main(String args[]) {
        int k = 3;
        int[] nums = {4 , 5 , 8 , 2};
        KthLargest stream = new KthLargest(k , nums);
        System.out.print(stream.add(3) + " ");
        System.out.print(stream.add(5) + " ");
        System.out.print(stream.add(10) + " ");
        System.out.print(stream.add(9) + " ");
        System.out.print(stream.add(4) + " ");
        System.out.println();
    }
}
4 5 5 8 8

스트림 Leetcode 솔루션에서 K 번째로 큰 요소의 복잡성 분석

시간 복잡성

O (N + Q)어디로 N = 초기 배열의 크기 (생성자를 호출하는 동안). Q = 쿼리 수. 이는 배열을 한 번 탐색하고 O (1) 시간에 각 쿼리에 응답하기 때문입니다.

공간 복잡성 

확인)어디로 K 주어진 인수입니다 (생성자를 호출하는 동안). 이는 일련의 작업 후에 힙 크기를 정확히 k로 유지하기 때문입니다.