शीर्ष K लगातार तत्वहरू


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन एप्पल ब्लूमबर्ग बाइटडेन्स राजधानी एक eBay फेसबुक गुगल माइक्रोसफ्ट बजेट पकेट रत्न
एरे हैश ह्याशिंग ढेर

समस्या वक्तव्य

शीर्ष K बारम्बार तत्वहरूमा हामीले एउटा दिन्छौं array nums [], K प्राय: आउने तत्त्वहरू पत्ता लगाउनुहोस्।

उदाहरण

nums[] = {1, 1, 1, 2, 2, 3}
k = 2
1 2

 

शीर्ष K लगातार तत्वहरू

nums[] = {1}
k = 1
1

शीर्ष K लगातार तत्वहरूको लागि भोली दृष्टिकोण

  1. निर्माण गर्नुहोस् नक्सा दिइएको एर्रेमा ट्र्यावर्सिंग गरेर तत्त्व र फ्रिक्वेन्सीको।
  2. फ्रिक्वेन्सीको घट्दो क्रम अनुसार नक्शाको प्रविष्टिहरू क्रमबद्ध गर्नुहोस्।
  3. क्रमबद्ध गरिएको नक्साको पहिलो k तत्वहरूले उत्तरमा योगदान दिन्छ।

उदाहरणका

nums [] = {१, १, २,,,,,,,} k र k = २

तत्व र आवृत्तिको नक्शा बनाउनुहोस्
नक्शा = {(१, २), (२, १), (,,)), (,, १)}

फ्रिक्वेन्सीको क्रम घट्दै क्रममा नक्शा क्रमबद्ध गर्नुहोस्
क्रमबद्ध नक्शा = {(,,)), (१, २), (२, १), (,, १)}

पहिलो k प्रविष्टिहरू उत्तरमा योगदान दिन्छ
उत्तर = 3 १

कोड

शीर्ष K लगातार तत्वहरूको लागि जाभा कोड

import java.util.*;

class TopKFrequentElements {
    private static void printKFrequent(int[] nums, int k) {
        // Length of nums array
        int n = nums.length;

        // Build the map from nums array
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // Sort the map, according to decreasing order of frequency and store in a set
        TreeSet<Element> set = new TreeSet<>(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return Integer.compare(o2.freq, o1.freq);
            }
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Element curr = new Element(entry.getKey(), entry.getValue());
            set.add(curr);
        }

        // First k elements of the sorted map contributes to the answer
        int index = 0;
        for (Element element : set) {
            System.out.print(element.value + " ");
            index++;
            if (index == k)
                break;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 1, 1, 2, 2, 3};
        int k = 2;

        printKFrequent(nums, k);

        // Example 2
        nums = new int[]{1};
        k = 1;

        printKFrequent(nums, k);
    }

    // class representing a element and value pair
    static class Element {
        int value;
        int freq;

        public Element(int value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }
}

C ++ शीर्ष K लगातार तत्वहरूको लागि कोड

#include <bits/stdc++.h>
using namespace std;

// structure representing a element and value pair
struct Element {
    int value;
    int freq;
    
    Element(int v, int f) {
        value = v;
        freq = f;
    }
};

// Comparator to sort elements according to decreasing order of frequency
struct ElemetComp {
    bool operator()(const Element &e1, const Element & e2) {
        return (e2.freq < e1.freq);
    }
};

void printKFrequent(int *nums, int k, int n) {
    // Build the map from nums array
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++) {
        if (map.find(nums[i]) == map.end()) {
            map.insert(make_pair(nums[i], 1));
        } else {
            map[nums[i]] = map.find(nums[i])->second + 1;
        }
    }
    
    // Sort the map, according to decreasing order of frequency and store in a set
    set<Element, ElemetComp> set;
    unordered_map<int, int>:: iterator itr;
    for (itr = map.begin(); itr != map.end(); itr++) {
        Element curr(itr->first, itr->second);
        set.insert(curr);
    }
    
    // First k elements of the sorted map contributes to the answer
    int index = 0;
    for (auto it = set.begin(); it != set.end(); it++) {
        cout<<it->value<<" ";
        index++;
        if (index == k)
            break;
    }
    cout<<endl;
}

int main() {
    // Example 1
    int nums[] = {1, 1, 1, 2, 2, 3};
    int k = 2;

    printKFrequent(nums, k, 6);

    // Example 2
    int nums2 = {1};
    k = 1;

    printKFrequent(nums, k, 1);
    
    return 0;
}

जटिलता विश्लेषण

समय जटिलता

O (N * log (N)), कारण हामीले नक्सा प्रयोग गरेका छौं। र नक्शाले तत्वहरूको सम्मिलित गर्न लग एन समय लिन्छ।

ठाउँ जटिलता

O (N), यहाँ हामी नक्सामा तत्वहरू घुसाइरहेका छौं, जुन यो ठाउँको लागि जिम्मेवार छ। हामीले N एलिमेन्ट्स हाल्नु भएकोले स्पेस जटिलता O (N) पनि हो। यहाँ, N ले भिन्न तत्वहरुको संख्या दर्शायो। सबैभन्दा नराम्रो अवस्थामा सबै नम्बरहरू भिन्न हुन सक्छन्।

शीर्ष K लगातार तत्वहरूको लागि अनुकूल दृष्टिकोण

उत्तम दृष्टिकोण भनेको तत्व र फ्रिक्वेन्सीको अधिकतम हिप बनाउनु हो, फ्रिक्वेन्सी अनुसार हिप के समयको शीर्ष हटाउँदा जवाफ दिन्छ।

  1. निर्माण गर्नुहोस् नक्सा दिइएको एर्रेमा ट्र्यावर्सिंग गरेर तत्त्व र फ्रिक्वेन्सीको।
  2. निर्माण गर्नुहोस् अधिकतम ढेर नक्शाबाट फ्रिक्वेन्सी अनुसार।
  3. हिप k को शीर्षहरू हटाउनुहोस् र यो उत्तर हो।

शीर्ष K लगातार तत्वहरूको लागि कोड

जावा कोड

import java.util.*;

class TopKFrequentElements {
    private static void printKFrequent(int[] nums, int k) {
        // Length of nums array
        int n = nums.length;

        // Build the map from nums array
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }

        // Construct a max heap of element and frequency according to frequency
        PriorityQueue<Element> heap = new PriorityQueue<>(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return Integer.compare(o2.freq, o1.freq);
            }
        });

        // Build heap
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            heap.add(new Element(entry.getKey(), entry.getValue()));
        }

        // First k elements of heap contributes to the answer
        for (int i = 0; i < k; i++) {
            System.out.print(heap.poll().value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        int nums[] = new int[]{1, 1, 1, 2, 2, 3};
        int k = 2;

        printKFrequent(nums, k);

        // Example 2
        nums = new int[]{1};
        k = 1;

        printKFrequent(nums, k);
    }

    // class representing a element and value pair
    static class Element {
        int value;
        int freq;

        public Element(int value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }
}

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

// structure representing a element and value pair
struct Element {
    int value;
    int freq;
    
    Element(int v, int f) {
        value = v;
        freq = f;
    }
};

// Comparator to sort elements according to decreasing order of frequency
struct ElementComp {
    bool operator()(const Element &e1, const Element & e2) {
        return (e1.freq < e2.freq);
    }
};

void printKFrequent(int *nums, int k, int n) {
    // Build the map from nums array
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++) {
        if (map.find(nums[i]) == map.end()) {
            map.insert(make_pair(nums[i], 1));
        } else {
            map[nums[i]] = map.find(nums[i])->second + 1;
        }
    }
    
    // Construct a max heap of element and frequency according to frequency
    priority_queue<Element, vector<Element>, ElementComp> heap;
    for (auto itr = map.begin(); itr != map.end(); itr++) {
        Element element(itr->first, itr->second);
        heap.push(element);
    }
    
    // First k elements of heap contributes to the answer
    for (int i = 0; i < k; i++) {
        Element curr = heap.top();
        heap.pop();
        cout<<curr.value<<" ";
    }
    cout<<endl;
}

int main() {
    // Example 1
    int nums[] = {1, 1, 1, 2, 2, 3};
    int k = 2;

    printKFrequent(nums, k, 6);

    // Example 2
    int nums2 = {1};
    k = 1;

    printKFrequent(nums, k, 1);
    
    return 0;
}

जटिलता विश्लेषण

समय जटिलता

O (k log N + N), यहाँ N तत्वहरूको संख्या हो। किनभने सबैभन्दा नराम्रो अवस्थामा इनपुटमा रहेका सबै नम्बरहरू भिन्न हुन सक्छन्।
O (लग N) कारक आउँछ अधिकतम ढेर वा प्राथमिकता लाममा तत्व घुसाउने समयको कारण।

ठाउँ जटिलता

O (N), किनभने हामी एन एलिमेन्टहरू ion खराब केस भण्डार गर्दैछौं। ठाउँ जटिलता रैखिक छ।

सन्दर्भ