Prerequisite:

先決條件：

• Hashing data structure

  散列數(shù)據(jù)結(jié)構(gòu)

• How to write user-defined comparator for priority queue STL in C++?

  如何在C ++中為優(yōu)先級(jí)隊(duì)列STL編寫用戶定義的比較器？

• How to sort a map based on values instead of value?

  如何根據(jù)值而不是值對(duì)地圖排序？

Problem statement:

問(wèn)題陳述：

Sort an array based on frequencies. The element having maximum frequency will come first. If two elements have the same frequency then the element coming first will appear first in the sorted array two.

根據(jù)頻率對(duì)數(shù)組排序。 具有最大頻率的元素將排在最前面。 如果兩個(gè)元素具有相同的頻率，則最先出現(xiàn)的元素將首先出現(xiàn)在排序數(shù)組2中。

Example:

例：

Input array: [1, 2, 3, 2, 3, 2, 1]After sorting frequency wise: [2, 2, 2, 1, 1, 3, 3]2 has the maximum frequency thus, it came first and since 1 and 3 have the same frequency, so, 1 came first preserving the order in the input array.

Solution:

解：

The idea is to create a hash table first which will store the frequency of unique elements. That can be created like below:

這個(gè)想法是首先創(chuàng)建一個(gè)哈希表，它將存儲(chǔ)唯一元素的頻率。 可以如下創(chuàng)建：

Hash function, h(x)=x but instead of storing key we will store the count

哈希函數(shù)h(x)= x，但是我們將存儲(chǔ)計(jì)數(shù)而不是存儲(chǔ)密鑰

Initially, hash table is empty.

最初，哈希表為空。

For each key in input array,Hash[key]++ End for

If we create the hash table from the above input array, it will be,

如果我們根據(jù)上面的輸入數(shù)組創(chuàng)建哈希表，它將是

Key Frequency 1 2 2 3 3 2

So now we need to sort the map based on the value instead of the key, but for the same frequencies, we need to preserve the key order(it’s order not key itself).

因此，現(xiàn)在我們需要根據(jù)值而不是鍵對(duì)映射進(jìn)行排序，但是對(duì)于相同的頻率，我們需要保留鍵順序(該順序不是鍵本身)。

To preserve the key order we require another hash table that would store the first position of the key. We will store that like below:

為了保留鍵順序，我們需要另一個(gè)哈希表，該哈希表將存儲(chǔ)鍵的第一個(gè)位置。 我們將像下面這樣存儲(chǔ)：

Say this hash table is named first_occurrence

假設(shè)此哈希表名為first_occurrence

For each key in input array,If first_occurence[key]==0: //not assignedfirst_occurence[key]=key index+1 End for

So after processing the input the hash table first_occurrence would be:

因此，在處理輸入后，哈希表first_occurrence將是：

Key First occurrence 1 1(0+1) 2 2(1+1 3 3(2+1)

So now rest of the task is to sort the hash table based on the map and based on first_occurrence hash table.

因此，現(xiàn)在剩下的任務(wù)是根據(jù)地圖和基于first_occurrence哈希表對(duì)哈希表進(jìn)行排序。

We will use the priority queue to sort this map based on our defined comparator where we will implement logic to sort by frequency value and first_occurrence hash table.

我們將使用優(yōu)先級(jí)隊(duì)列根據(jù)定義的比較器對(duì)此映射表進(jìn)行排序，在該比較器中，我們將實(shí)現(xiàn)按頻率值和first_occurrence哈希表排序的邏輯。

How to pass this in the comparator is our main challenge or area of our discussion?

如何在比較器中傳遞這一點(diǎn)是我們的主要挑戰(zhàn)還是我們討論的領(lǐng)域？

You can observe a thing that we have designed a class for this problem and kept the first_occurrence hash table as a data member, not any local member to a function. Thing is not the thing I do in general. So, there must be something, that made me design a class and bring the OOP concept within it. This is because I need to feed the first_occurrence hash table into the comparator and the comparator is a lambda function. Like below,

您會(huì)發(fā)現(xiàn)，我們已經(jīng)為此問(wèn)題設(shè)計(jì)了一個(gè)類，并將first_occurrence哈希表保留為數(shù)據(jù)成員，而不是函數(shù)的任何本地成員。 總的來(lái)說(shuō)，這不是我要做的事情。 因此，必須有某種東西使我設(shè)計(jì)了一個(gè)類并將OOP概念引入其中。 這是因?yàn)槲倚枰獙irst_occurrence哈希表提供給比較器，并且比較器是lambda函數(shù)。 像下面一樣

auto comp=[](pair<int,int> a, pair<int,int> b){//function body }But this time if you notice the implementation, we have auto comp=[this](pair<int,int> a, pair<int,int> b){//function body }

This helps you to pass the data members to the lambda function or it's known as capturing of the lambda function.

這可以幫助您將數(shù)據(jù)成員傳遞給lambda函數(shù)，或者稱為捕獲lambda函數(shù) 。

That's why we designed the class and made first_occurrence as data members to feed into the lambda function. Now we can perform our logic similarly as we do in comparators.

這就是為什么我們?cè)O(shè)計(jì)類并讓first_occurrence作為數(shù)據(jù)成員饋入lambda函數(shù)的原因。 現(xiàn)在，我們可以像在比較器中一樣執(zhí)行邏輯。

The lambda comparator would be like below which will give us a sorted map based on our requirement via the priority_queue.

Lambda比較器如下所示，它將根據(jù)優(yōu)先級(jí)通過(guò)priority_queue為我們提供排序的映射。

auto comp=[this](pair<int,int> a, pair<int,int> b){ if(a.second<b.second)return true;else if(a.second>b.second)return false;else{if(first_occurence[a.first]<first_occurence[b.first])return false;elsereturn true;} };

So after pushing all pairs(a map element is pair, <key, element>) we will have our priority queue as,

因此，在推送所有對(duì)之后(一個(gè)地圖元素是pair，<key，element>)，我們將擁有優(yōu)先級(jí)隊(duì)列，

Key Frequency 2 3 1 2 3 2

Now, pop each element from the priority queue and append the key as many times as the frequency,

現(xiàn)在，從優(yōu)先級(jí)隊(duì)列中彈出每個(gè)元素，并按頻率添加鍵多次，

So at iteration 1 We will pop <2,3> So vector will be 2 2 2 So at iteration 2 We will pop <1,2> So vector will be 2 2 2 1 1 So at iteration 3 We will pop <3,2> So vector will be 2 2 2 1 1 3 3 Queue Is empty So our sorted array based on frequency is 2 2 2 1 1 3 3

C++ implementation:

C ++實(shí)現(xiàn)：

#include <bits/stdc++.h> using namespace std;class Includehelp { public:unordered_map<int, int> first_occurence;void print(vector<int> arr){for (auto i : arr) {cout << i << " ";}cout << endl;}vector<int> sort_by_frequency(vector<int> arr){//create the hashmapunordered_map<int, int> mymap;for (int i = 0; i < arr.size(); i++) {mymap[arr[i]]++;if (first_occurence[arr[i]] == 0)first_occurence[arr[i]] = i + 1;}//now to sort based on frequency lets use priority queue//comparator of priority queue using lambda functionauto comp = [this](pair<int, int> a, pair<int, int> b) {if (a.second < b.second)return true;else if (a.second > b.second)return false;else {if (first_occurence[a.first] < first_occurence[b.first])return false;elsereturn true;}};priority_queue<pair<int, int>, vector<pair<int, int> >, decltype(comp)> pq(comp);for (auto& ij : mymap) {pq.push(ij);}//sorted outcomevector<int> result;while (!pq.empty()) {pair<int, int> p = pq.top();pq.pop();int no = p.first;int freq = p.second;for (int i = 0; i < freq; i++)result.push_back(no);}return result;} };int main() {int n;cout << "Enter number of elements\n";cin >> n;vector<int> arr(n, 0);cout << "Enter the elements\n";for (int i = 0; i < n; i++) {cin >> arr[i];}Includehelp* obj = new Includehelp();arr = obj->sort_by_frequency(arr);cout << "Printing after sorting by frequency\n";obj->print(arr);return 0; }

Output:

輸出：

Enter number of elements 8 Enter the elements 1 2 3 1 2 3 4 5 Printing after sorting by frequency 1 1 2 2 3 3 4 5

翻譯自: https://www.includehelp.com/data-structure-tutorial/sort-elements-by-frequency.aspx

總結(jié)

以上是生活随笔為你收集整理的按频率对元素进行排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。