Kth бузургтарин унсур дар ҳалли Leetcode ҳалли  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon себ Қуттии мехаранд Facebook Голдман Sachs Google Microsoft Нутаниx
Алгоритм алгоритмҳо рамзгузорӣ лоиҳа Андозаи мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Изҳороти мушкилот  

Дар ин мушкилот, мо бояд як синфро таҳия кунем KthLargest () ки дар ибтидо адади бутуни k ва an дорад асал ададҳо. Мо бояд ҳангоми бунёди k ва массив барои он конструктори параметршуда бинависем нум ҳамчун далел қабул карда мешаванд. Синф инчунин вазифа дорад илова кардан (вал) ки унсури наверо бо арзиш илова мекунад Вал ба ҷараёни ададҳо. Барои ҳар як илова кардан () занг занед, мо бояд як адади бутуни баргардонем, ки он Kth унсури калонтарин дар ҷараёни равон аст.

мисол

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

Шарҳ:

Kth бузургтарин унсур дар ҳалли Leetcode ҳалли

Равиш (Тӯдаҳои камтар)  

Ҳар вақте ки сухан дар бораи ёфтани унсури хурдтарин / калонтарини Kth меравад, тақрибан ҳар лаҳза тӯдаҳои max / min ба мақсад хидмат мекунанд. Ин аз сабаби хусусияти чандирии онҳо барои нигоҳ доштани унсурҳо дар шакли мураттаб (афзалиятнок) ба назар мерасад. Дар ин ҷо, мо метавонистем массивро барои дар худ доштани унсурҳо ҳангоми пурсиш истифода барем. Аммо, барои пайдо кардани Kth унсури калонтарин дар массив, мо бояд барои ҳар як дархост вақти O (N) -ро истифода барем. Аз ин рӯ, мо метавонем миқдори минаҳоеро нигоҳ дорем, ки андозаи k-ро дар вақти O (1) пайдо кунад. Аҳамият диҳед, ки азбаски мо min-heap -ро истифода мебарем, унсури болотарин дар теппа хурдтарин хоҳад буд. Ва азбаски мо пас аз ҳар як пурсиш ҳаҷми теппаро ба k баробар кардем, ин унсури боло K-и калонтарин дар ҷараёни умумӣ хоҳад буд (зеро теппа танҳо k элементҳои калонтаринро нигоҳ медорад).

ҳамчунин нигаред
Оҳиста ҳалли Leetcode калиди

Татбиқи унсури Kth бузургтарин дар ҳалли Leetcode Stream

Барномаи 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

Таҳлили мураккабии элементҳои Kth бузургтарин дар ҳалли Leetcode Stream

Мураккабии вақт

O (N + Q), ки дар он N = андозаи массиви ибтидоӣ (ҳангоми занг задан ба созанда). Q = Шумораи дархостҳо. Ин аз он сабаб аст, ки мо массивро як маротиба тай карда, ба ҳар як савол дар вақти O (1) ҷавоб медиҳем.

Мураккабии фазо 

ХУБ), ки дар он K далели додашуда мебошад (ҳангоми даъват кардани конструктор). Ин аз он сабаб аст, ки мо андозаи теппаҳоро пас аз ҳар гуна амалиёт маҳз k k нигоҳ медорем.

ҳамчунин нигаред
String Shift Leetcode -ро иҷро кунед