Bir Axın Leetcode həllində ən böyük element

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma qutu eBay Facebook Goldman Sachs google microsoft Nutanix
Alqoritm alqoritmlər kodlaşdırma Layihə Yığın müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 97

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bu problemdə bir sinif dizayn etməliyik KthLargest () əvvəlcə k və an tam ədədi var array tam ədədi. Tam bir k və sıra olduqda bunun üçün parametrləşdirilmiş bir konstruktor yazmalıyıq nömrə arqument kimi qəbul edilir. Sinifin də bir funksiyası var əlavə et (val) dəyəri olan yeni bir element əlavə edir val tam ədəd axınına. Hər biri üçün əlavə et () çağırırıq, axındakı axındakı ən böyük element olan bir tam ədədi qaytarmalıyıq.

misal

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

Explanation:

Bir Axın Leetcode həllində ən böyük elementPin

Yanaşma (Min yığınlar)

Kth ən kiçik / ən böyük elementi tapmağa gəldikdə, demək olar ki, hər dəfə maks / min yığınlar məqsədə xidmət edir. Bunun səbəbi elementləri sıralanmış (prioritetli) bir şəkildə tutmaq üçün çevik təbiətidir. Burada bir sorğu edildikdə elementləri ehtiva edən bir sıra istifadə edə bilərik. Ancaq tapmaq üçün Dizidəki ən böyük element, hər bir sorğu üçün O (N) vaxtından istifadə etməliyik. Buna görə də, O (1) vaxtında k ən böyük elementi tapmaq üçün k ölçüsündə bir min yığın saxlaya bilərik. Diqqət yetirin ki, bir yığın istifadə etdiyimiz üçün, ən üst element yığındakı ən kiçik olardı. Yığın ölçüsünü hər sorğudan sonra k-yə bərabər tutduğumuzdan, bu üst element ümumi axındakı K ən böyük olacaqdır (yığın yalnız k ən böyük elementi saxlayacağı üçün).

Bir Axın Leetcode həllində Kth Ən Böyük Elementin tətbiqi

C ++ Proqramı

#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 Proqramı

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

Bir Axın Leetcode həllində Kth Ən Böyük Elementin Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N + Q), Harada N = ilkin massivin ölçüsü (konstruktoru çağırarkən). Q = Sorğuların sayı. Bunun səbəbi serialı bir dəfə keçdiyimiz və hər bir sorğuya O (1) vaxtında cavab verdiyimizdir.

Kosmik Mürəkkəblik 

TAMAM), Harada K verilmiş arqumentdir (konstruktoru çağırarkən). Bunun səbəbi, hər hansı bir əməliyyatdan sonra yığın ölçüsünü tam olaraq k olaraq saxlamağımızdır.

Crack Sistemi Dizayn Müsahibələri
Translate »
1