Leetcode шийдлийн урсгалын хамгийн том элемент


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Хайрцаг Ebay Facebook-ийн Goldman Sachs Google-ийн Microsoft- Nutanix
Алгоритм Зураг төсөл боловсруулах Нуруулаг

Асуудлын мэдэгдэл

Энэ асуудалд бид анги зохиох ёстой KthLargest () эхэндээ k ба an гэсэн бүхэл тоотой байна массив бүхэл тоонууд. Бид бүхэл тоо k ба массив байхад параметржүүлсэн байгуулагч бичих хэрэгтэй тоохгүй аргумент байдлаар дамжуулагддаг. Анги нь бас чиг үүрэгтэй нэмэх (val) Энэ нь үнэ цэнэтэй шинэ элемент нэмдэг Нэрлэсэн үнэ бүхэл тоон урсгалд. Тус бүр нэмэх () дуудлага хийвэл бид урсгал урсгалын хамгийн том K элемент болох бүхэл тоог буцаах хэрэгтэй.

Жишээ нь

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

Тайлбар:

Leetcode шийдлийн урсгалын хамгийн том элемент

Хандалт (Хамгийн бага овоо)

Kth хамгийн бага / хамгийн том элементийг олох тухай бүрт max / min овоолго нь зорилгодоо хүрдэг. Энэ нь элементүүдийг эрэмбэлсэн (тэргүүлэх ач холбогдол бүхий) хэлбэрээр барих уян хатан шинж чанартай учраас юм. Энд бид асуулт тавих болгонд элементүүдийг агуулсан массив ашиглаж болох байсан. Гэхдээ олохын тулд Массив дахь хамгийн том элемент, бид асуулт бүрт O (N) цагийг ашиглах ёстой. Тиймээс бид O (1) хугацааны k элементийн хамгийн том элементийг олохын тулд хамгийн бага k овоолгыг хадгалах боломжтой. Бид мин-овоо ашиглаж байгаа тул хамгийн дээд элемент нь овоолго дотор хамгийн бага байх болно гэдгийг анхаарна уу. Асуулт бүрийн дараа бид овоолгын хэмжээг k-тэй тэнцүү хэмжээгээр холбосон тул энэ дээд элемент нь нийт урсгал дахь Kth хамгийн том хэмжээтэй байх болно (овоолго нь зөвхөн k хамгийн том элементүүдийг хадгалах тул).

Lethcode шийдэл дэх Kth хамгийн том элементийг хэрэгжүүлэх

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

Java програм

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 уусмал дахь Kth хамгийн том элементийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N + Q), хаана N = анхны массивын хэмжээ (байгуулагчийг дуудаж байх үед). Q = Асуулгын тоо. Учир нь бид массивыг нэг удаа туулж, асуулга бүрт O (1) цагт хариулдаг.

Сансрын нарийн төвөгтэй байдал 

БОЛЖ БАЙНА УУ), хаана K нь өгөгдсөн аргумент юм (байгуулагчийг дуудаж байх үед). Учир нь бид аливаа үйл ажиллагааны дараа овоолгын хэмжээг яг k байхаар хадгалдаг.