ટોચના કે વારંવાર તત્વો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance કેપિટલ વન ઇબે ફેસબુક Google માઈક્રોસોફ્ટ ઓરેકલ પોકેટ જેમ્સ
અરે હેશ હેશિંગ .ગલો

સમસ્યા નિવેદન

ટોચના કે વારંવાર આવનારા તત્વોમાં આપણે એ એરે નંબ્સ [], કે સૌથી વધુ વારંવાર બનતા તત્વો શોધો.

ઉદાહરણો

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

 

ટોચના કે વારંવાર તત્વો

nums[] = {1}
k = 1
1

ટોચના કે વારંવાર આવનારા તત્વો માટે નિષ્કપટ અભિગમ

  1. એક બનાવો નકશો આપેલ એરેમાં ટ્રversવર્સ કરીને તત્વ અને આવર્તન.
  2. આવર્તનના ઘટતા ક્રમમાં નકશાની પ્રવેશોને સortર્ટ કરો.
  3. સ kર્ટ કરેલા નકશાના પ્રથમ કે તત્વો જવાબમાં ફાળો આપે છે.

ઉદાહરણ

સંખ્યાઓ [] = {1, 1, 2, 3, 3, 3, 4} અને k = 2

તત્વો અને આવર્તનનો નકશો બનાવો
નકશો = {(1, 2), (2, 1), (3, 3), (4, 1)}

આવર્તનના ઘટતા ક્રમમાં નકશાને સortર્ટ કરો
સ mapર્ટ કરેલો નકશો = {(,,)), (3, 3), (1, 2), (2, 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;
}

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન * લ logગ (એન)), કારણ કે આપણે નકશોનો ઉપયોગ કર્યો છે. અને નકશા તત્વોના નિવેશ માટે લોગ એનનો સમય લે છે.

અવકાશ જટિલતા

ઓ (એન), અહીં અમે નકશામાં તત્વો શામેલ કરીએ છીએ, જે આ જગ્યા માટે જવાબદાર છે. આપણે એન તત્વો શામેલ કર્યા હોવાથી, અવકાશ જટિલતા પણ ઓ (એન) છે. અહીં, એન અલગ તત્વોની સંખ્યા દર્શાવે છે. સૌથી ખરાબ કિસ્સામાં, બધી સંખ્યાઓ અલગ હોઇ શકે.

ટોચના કે વારંવાર તત્વો માટે શ્રેષ્ઠ અભિગમ

તત્વ અને આવર્તનનો મહત્તમ apગલો બનાવવાનો વધુ સારો અભિગમ, આવર્તન અનુસાર, kગલાની ટોચની ટોચને દૂર કરવાથી જવાબ મળે છે.

  1. એક બનાવો નકશો આપેલ એરેમાં ટ્રversવર્સ કરીને તત્વ અને આવર્તન.
  2. એક બનાવો મહત્તમ apગલો નકશા પરથી આવર્તન અનુસાર.
  3. Apગલાની ટોચની વખત દૂર કરો અને આ જવાબ છે.

ટોચના કે વારંવાર આવનારા તત્વો માટેનો કોડ

જાવા કોડ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (કે લ logગ એન + એન), અહીં N એ તત્વોની સંખ્યા છે. કારણ કે સૌથી ખરાબ કિસ્સામાં ઇનપુટમાં હાજર બધી સંખ્યાઓ અલગ હોઈ શકે છે.
ઓ (લ Nગ એન) પરિબળ મહત્તમ apગલા અથવા અગ્રતા કતારમાં તત્વ શામેલ કરવાના સમયને કારણે આવે છે.

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે N તત્વો આયન સૌથી ખરાબ કિસ્સામાં સંગ્રહિત કરીએ છીએ. જગ્યાની જટિલતા રેખીય છે.

સંદર્ભ