ធាតុធំជាងគេបំផុតរបស់ខេតនៅក្នុងដំណោះស្រាយស្ទ្រីមលេយកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ប្រអប់ របស់ eBay Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft ផ្លែល្ហុង
ក្បួនដោះស្រាយ រចនាដោយ គំនរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវរចនាថ្នាក់មួយ ខេតឡារ៉ូត () ដំបូងមានចំនួនគត់ k និងមួយ អារេ នៃចំនួនគត់។ យើងត្រូវសរសេរអ្នកសាងសង់ដែលមានប៉ារ៉ាម៉ែត្រសម្រាប់វានៅពេលចំនួនគត់ k និងអារេ លេខ ត្រូវបានអនុម័តជាអាគុយម៉ង់។ ថ្នាក់ក៏មានមុខងារផងដែរ បន្ថែម (តម្លៃ) ដែលបន្ថែមធាតុថ្មីជាមួយតម្លៃ តម្លៃ ចូលទៅក្នុងស្ទ្រីមនៃចំនួនគត់។ សម្រាប់គ្នា បន្ថែម () ការហៅ, យើងត្រូវត្រឡប់លេខគត់ដែលជាធាតុធំបំផុតរបស់ខេតនៅក្នុងចរន្តរត់។

ឧទាហរណ៍

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

ការពន្យល់:

ធាតុធំជាងគេបំផុតរបស់ខេតនៅក្នុងដំណោះស្រាយស្ទ្រីមលេយកូដ

វិធីសាស្រ្ត (មីនហេហេ)

រាល់ពេលដែលរកឃើញធាតុតូចបំផុត / ធំជាងគេបំផុតរបស់ខេតនោះអតិបរិមា / នាទីនឹងកើនឡើងស្ទើរតែរាល់ពេលបម្រើគោលបំណង។ នេះគឺដោយសារតែធម្មជាតិដែលអាចបត់បែនបានរបស់ពួកគេក្នុងការកាន់ធាតុនៅក្នុងរបៀបដែលបានតម្រៀប (ផ្តល់អាទិភាព) ។ នៅទីនេះយើងក៏អាចប្រើអារេមួយដើម្បីផ្ទុកធាតុរាល់ពេលដែលសំណួរត្រូវបានធ្វើឡើង។ ប៉ុន្តែដើម្បីស្វែងរក ធាតុធំបំផុតរបស់ខេតនៅក្នុងអារេ, យើងត្រូវតែប្រើពេលវេលាអូ (N) សម្រាប់សំណួរនីមួយៗ។ ដូច្ន្រះយើងអាចថ្រាំតូចមួយបៃនៃទំហំ k ដើម្របីរកឃើញធាតុធំបំផុតទី ១ ក្នុងរយៈព្រលអូ (១) ។ ចំណាំថាចាប់តាំងពីយើងកំពុងប្រើមីបហបធាតុដែលខ្ពស់ជាងគេនឹងតូចជាងគេបំផុតនៅក្នុងគំនរ។ ហើយដោយសារយើងបានភ្ជាប់ទំហំហ៊ាស្មើនឹង k បន្ទាប់ពីសំណួរនីមួយៗធាតុកំពូលនេះនឹងធំជាងគេបំផុតនៅស្ទ្រីមទាំងមូល (ដូចជាហ៊ានឹងរក្សាទុកធាតុ 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

ការវិភាគភាពស្មុគស្មាញនៃធាតុធំបំផុតខេតនៅក្នុងដំណោះស្រាយស្ទ្រីមឡេឡេកូដ

ស្មុគស្មាញពេលវេលា

O (N + Q), ដែលជាកន្លែងដែល N = ទំហំនៃអារេដំបូង (ពេលហៅអ្នកសាងសង់) ។ Q = ចំនួនសំណួរ។ នេះគឺដោយសារតែយើងឆ្លងកាត់អារេម្តងហើយឆ្លើយសំណួរនីមួយៗក្នុងរយៈពេលអូ (1) ។

ភាពស្មុគស្មាញនៃលំហ 

យល់ព្រម), ដែលជាកន្លែងដែល K គឺជាអាគុយម៉ង់ដែលបានផ្តល់ឱ្យ (ខណៈពេលដែលហៅអ្នកសាងសង់) ។ នេះក៏ព្រោះតែយើងរក្សាទំហំហ៊ារអោយនៅជាគរបន្ទាប់ពីមានប្រតិបត្ដិការណាមួយ។