مٿين جي اڪثر عنصر


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ايپل Bloomberg ByteDance گاديء جو هڪ eBay ڪريو گوگل Microsoft جي Oracle کيسي جواٽ
ڪيريو هاش هاشمي هوپ

مسئلي جو بيان

مٿيون اڪثر عنصر اسان هڪ ڏنو آهي صف نمل [] ، ڳوليو آھن اڪثر اڪثر عنصر.

مثال

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} ۽ k = 2

عناصر ۽ فريڪوئنسي جو نقشو ٺاھيو
نقشو = {(1 ، 2) ، (2 ، 1) ، (3 ، 3) ، (4 ، 1)}

فريڪئنسي جي گھٽتائي واري ترتيب ۾ نقشي کي ترتيب ڏيو
ترتيب وار نقشو = {(3، 3)، (1، 2)، (2، 1)، (4، 1)}

پهرين ڪ اندراج جواب ۾ حصو وٺندو آهي
ANS = 3 1

ڪوڊ

جاوا ڪوڊ لاءِ مٿين 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;
        }
    }
}

مٿي + ڪ اڪثر عنصر لاءِ سي ++ ڪوڊ

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (k لاگ اين + اين)هتي اين عنصرن جو تعداد آهي. ڇاڪاڻ ته بدترين حالت ۾ انپٽ ۾ موجود سمورا انگ ڌار هوندا.
اي (لاگ اين) عنصر ڇاڪاڻ ته عنصر کي وڌ ۾ وڌ شيپ ۾ شامل ڪرڻ جي ترجيح يا ترجيح قطار ۾.

خلائي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان سڀني کان بدترين ڪيس N عنصرن کي محفوظ ڪري رهيا آهيون. خلائي پيچيدگي لڪير آھي.

حوالا