Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Discover occurrences of Mth most frequent component of Array

[ad_1]

Given an array arr[], integer M and queries, the duty is to search out the question[i]th question of Mth most frequent component of the array.

Examples:

Enter: arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2},  M = 1, question[] = {100, 4, 2}
Output: -1, 12, 5
Clarification: Right here most frequent Integer = 8, with frequency = 4
Thus for Question
1) For okay = 100, Output-> -1 (one hundredth component not obtainable)
2) For okay = 4, Output -> 12 (4th incidence of 8 is at twelfth index)
3) For okay = 2, Output -> 5 (2nd occurrece of 8 is at fifth index)

Enter: arr[] = {2, 2, 20, 8, 8, 1, 2, 5}, M = 2, question[] = {2, 3}
Output: 4, -1

 

Method: The answer of the issue relies on the next thought:

Discover the Mth most frequent component. Then retailer all of the occurrences of the integers and discover the question[i]th incidence of the Mth most frequent component.

Comply with the steps talked about beneath to implement the concept:

  • Declare map for integer and vector. 
  • Traverse by the enter array and retailer the distinctive components within the map as keys. 
    • Then push the index of the occurrences of that component into the vector. 
  • Retailer the distinctive components with their frequency and discover the Mth most frequent component.
  • Once more traverse by the queries.
    • For every question, test if Okay < vector measurement then return -1.
    • Else retailer the indexes of the component.

Comply with the beneath illustration for a greater understanding

Illustration:

arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2}, M = 1
Query_val = {100, 4, 2}

Now for Every component the frequency and occured indexes are:

1  -> 1, 6           frequency : 2
2  -> 2, 7, 13     frequency : 3
20 -> 3              frequency : 1
8  -> 4, 5, 9, 12  frequency : 4
5  -> 8               frequency : 1
0  -> 10             frequency : 1
6  -> 11             frequency : 1

Thus most frequency component = 8 with frequency 4

Now for queries
For okay = 100, -> -1  (okay > maxfre)
For Okay = 4,   -> 12  ((Okay-1) index of vector) 
For Okay = 2,   -> 5   ((Okay-1) index of vector)   

Under is the implementation of the above strategy: 

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

vector<int> findindexes(vector<int> arr, int M,

                        vector<int> question)

{

    

    

    

    unordered_map<int, vector<int> > fre;

    int n = arr.measurement();

  

    

    

    vector<int> ans;

  

    for (int i = 0; i < n; i++) {

  

        

        

        fre[arr[i]].push_back(i + 1);

    }

  

    set<pair<int, int> > st;

    for (auto it = fre.start();

         it != fre.finish(); it++) {

        st.insert({ it->second.measurement(),

                    it->first });

    }

  

    int maxelement, i = 0;

    for (auto it = st.rbegin(); it != st.rend()

                                and that i < M;

         it--, i++) {

        maxelement = (*it).second;

    }

  

    for (int i = 0; i < question.measurement(); i++) {

  

        

        if (fre[maxelement].measurement() < question[i])

            ans.push_back(-1);

        else {

  

            

            

            ans.push_back(

                fre[maxelement][query[i] - 1]);

        }

    }

  

    return ans;

}

  

int essential()

{

    

    vector<int> arr

        = { 1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2 };

    int M = 1;

    vector<int> question = { 100, 4, 2 };

  

    

    vector<int> ans = findindexes(arr, M, question);

    for (int i = 0; i < ans.measurement(); i++) {

        cout << ans[i] << " ";

    }

    return 0;

}

Time Complexity: O(N + Q + Okay * logK) Q = Variety of queries, Okay = variety of distinctive components.
Auxiliary Area: O(N)

[ad_2]

Leave a Reply