शीर्ष K बारंबार तत्व


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग ByteDance एक राजधानी ईबे Facebook गूगल माइक्रोसॉफ्ट ओरेकल पॉकेट रत्न
ऐरे हैश hashing ढेर

समस्या का विवरण

शीर्ष कश्मीर में अक्सर तत्वों हम एक दिया है सरणी संख्या [], k को सबसे अधिक बार होने वाले तत्वों का पता लगाएं।

उदाहरण

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

 

शीर्ष K बारंबार तत्व

nums[] = {1}
k = 1
1

शीर्ष कश्मीर आवृत्ति तत्वों के लिए Naive दृष्टिकोण

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

उदाहरण

nums [] = {१, १, २, ३, ३, ३, ४} और के = २

तत्वों और आवृत्ति का मानचित्र बनाएँ
नक्शा = {(१, २), (२, १), (३, ३), (४, १)}

आवृत्ति के घटते क्रम में मानचित्र को क्रमबद्ध करें
क्रमबद्ध मानचित्र = {(3, 3), (1, 2), (2, 1), (4, 1)}

पहले k प्रविष्टियाँ उत्तर में योगदान करती हैं
उत्तर = 3 1

कोड

शीर्ष कश्मीर आवृत्ति तत्वों के लिए जावा कोड

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 ++ शीर्ष कश्मीर आवृत्ति तत्वों के लिए कोड

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

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

समय जटिलता

ओ (एन * लॉग (एन)), कारण हमने एक मानचित्र का उपयोग किया है। और तत्वों के सम्मिलन के लिए नक्शा लॉग एन समय लेता है।

अंतरिक्ष जटिलता

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

शीर्ष कश्मीर आवृत्ति तत्वों के लिए इष्टतम दृष्टिकोण

एक बेहतर दृष्टिकोण तत्व और आवृत्ति का अधिकतम ढेर बनाना है, आवृत्ति के अनुसार, ढेर के समय के शीर्ष को हटाने से उत्तर मिलता है।

  1. एक निर्माण नक्शा तत्व और आवृत्ति दिए गए सरणी में ट्रैवर्स करके।
  2. एक निर्माण अधिकतम ढेर नक्शे से आवृत्ति के अनुसार।
  3. ढेर कश्मीर समय के शीर्ष निकालें और यह जवाब है।

शीर्ष कश्मीर आवृत्ति तत्वों के लिए कोड

जावा कोड

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 तत्वों की संख्या है। क्योंकि सबसे खराब स्थिति में इनपुट में मौजूद सभी नंबर अलग हो सकते हैं।
ओ (लॉग एन) कारक अधिकतम हीप या प्राथमिकता कतार में एक तत्व डालने के समय के कारण आता है।

अंतरिक्ष जटिलता

पर), क्योंकि हम एन तत्वों आयन सबसे खराब स्थिति भंडारण कर रहे हैं। अंतरिक्ष की जटिलता रैखिक है।

संदर्भ