c++ - 获取给定数字集中具有相同数字频率的组数

Question

这是我在面试中遇到的一个问题，我想知道最好的方法是什么。 给出了一个数字列表，我们需要确定每个数字的数字具有相同频率的组数并打印这些组。例如: 例如，如果数字是: 1 10 3 33

有 4 个组:

G1={1}has one 1. 
G2={3} has one 3. 
G3={10}has one 1 and one 0. 
G4={33}as two 3s.

我正在考虑保留 map vector 。 map 将包含每个数字的频率。现在，当一个数字到来时，检查整个 vector 中是否存在与当前数字具有相同频率图的条目。如果存在则追加到列表中。我无法确定应该如何识别组以及打印它。有没有更好的方法来解决这个问题，因为我觉得我的解决方案效率很低。

Answer 1

考虑一下哈希表是如何工作的。您将哈希函数应用于该项目，并根据该哈希值将该项目分配给一个槽。但可能会出现两个不同的项具有相同的哈希值。在这种情况下，哈希表将创建具有相同哈希值的值列表。这称为碰撞。

在哈希表实现中，我们尝试避免冲突。但在这里它会很好地为你服务。如果您可以找到一个哈希函数，使得:同一组中的两个数字具有相同的哈希值，您就可以轻松地将这些数字分组。

此类哈希函数的示例如下:

• 将数字转换为字符串
• 按升序对字符串进行排序

同一组中的所有数字将具有相同的哈希值。

实现示例:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;


unordered_map<string, vector<int>> group_numbers(vector<int> numbers) {
    unordered_map<string, vector<int>> results;
    for(auto n : numbers) {
        stringstream buffer;
        buffer << n;
        string hash;
        buffer >> hash;

        sort(begin(hash), end(hash));
        results[hash].push_back(n);
    }
    return results;
}


int main() {
    vector<int> numbers{1, 10, 3, 33, 133, 331, 313, 333};
    auto results = group_numbers(numbers);
    int group = 0;
    for(auto kv : results) {
        cout << "Group " << (++group) << " : ";
        copy(begin(kv.second), end(kv.second),
             ostream_iterator<int>(cout, " "));
        cout << "\n";
    }
}

然后运行时打印:

Group 1 : 333
Group 2 : 133 331 313
Group 3 : 1
Group 4 : 10
Group 5 : 33
Group 6 : 3