शीर्ष के वारंवार घटक  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सफरचंद ब्लूमबर्ग बाइट डान्स कॅपिटल वन हा कोड eBay फेसबुक Google मायक्रोसॉफ्ट ओरॅकल पॉकेट रत्ने
अरे हॅश हॅशिंग ढीग

समस्या विधान  

शीर्ष के मध्ये वारंवार घटक दिले आहेत अॅरे nums [] मध्ये, के वारंवार आढळणारे घटक शोधा.

उदाहरणे  

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

 

शीर्ष के वारंवार घटकपिन

nums[] = {1}
k = 1
1

टॉप के वारंवार घटकांकरिता भोळे दृष्टिकोन  

  1. बिल्ड ए नकाशा दिलेल्या अ‍ॅरेमध्ये ट्रॅव्हर्स करून घटक आणि वारंवारता
  2. वारंवारतेच्या घटत्या क्रमानुसार नकाशाच्या नोंदीची क्रमवारी लावा.
  3. क्रमवारी लावलेल्या नकाशाचे प्रथम के घटक उत्तरावर सहयोग करतात.

उदाहरण

संख्या [] = {1, 1, 2, 3, 3, 3, 4} आणि के = 2

घटक आणि वारंवारतेचा नकाशा तयार करा
नकाशा = {(1, 2), (2, 1), (3, 3), (4, 1)}

वारंवारतेच्या क्रमाने नकाशाची क्रमवारी लावा
क्रमवारीकृत नकाशा = {(3, 3), (1, 2), (2, 1), (4, 1)}

प्रथम के नोंदी उत्तरात योगदान देतात
उत्तर = 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;
        }
    }
}

शीर्ष के वारंवार वारंवार घटकांसाठी सी ++ कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * लॉग (एन)), कारण आम्ही एक नकाशा वापरला आहे. आणि घटक समाविष्ट करण्यासाठी नकाशा लॉग एन वेळ घेते.

हे सुद्धा पहा
दिलेल्या पालक अ‍ॅरेच्या प्रतिनिधित्त्वातून बायनरी ट्री बांधा

स्पेस कॉम्प्लेक्सिटी

ओ (एन), येथे आम्ही नकाशामध्ये घटक समाविष्ट करीत आहोत, जे या जागेसाठी जबाबदार आहे. आम्ही एन घटक समाविष्ट केल्यामुळे स्पेस कॉम्प्लेक्सिटी देखील ओ (एन) आहे. येथे एनने भिन्न घटकांची संख्या दर्शविली. सर्वात वाईट परिस्थितीत, सर्व संख्या भिन्न असू शकतात.

टॉप के वारंवार घटकांकरिता इष्टतम दृष्टीकोन  

घटक आणि वारंवारतेचा जास्तीत जास्त ढीग बनविणे हा एक चांगला दृष्टिकोन आहे, वारंवारतेनुसार, ढीग केच्या वेळाची शीर्ष काढून टाकल्यास उत्तर मिळेल.

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

सी ++ कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (के लॉग एन + एन)येथे एन घटकांची संख्या आहे. कारण सर्वात वाईट परिस्थितीत इनपुटमध्ये उपस्थित सर्व संख्या भिन्न असू शकतात.
ओ (लॉग एन) घटक जास्तीत जास्त ढीग किंवा प्राधान्य रांगेत घटक घालण्याची वेळ असल्यामुळे येतो.

हे सुद्धा पहा
सिंगल लिंक्ड यादी वापरुन प्राधान्य रांग

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही सर्वात वाईट प्रकरणात एन घटक आयन संचयित करत आहोत. जागेची जटिलता रेखीय आहे.

संदर्भ