获取在给定的一组数字中具有相同数字频率的组数。
获取在给定的一组数字中具有相同数字频率的组数。
提问于 2016-04-22 18:05:40
这是我在一次面试中遇到的一个问题，我想知道最好的方法是什么。给出了一个数字列表，我们需要识别每个数字的数字具有相同频率的组数，并打印这些组。例如:如果数字为: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.我在考虑保留一个地图矢量。这些地图将包含每个数字的频率。现在，当一个数字出现时，请检查整个向量中是否存在一个条目，该条目将具有当前数字的相同频率映射。如果它存在，请追加到列表中。我无法确定我应该如何识别组以及打印它。有没有更好的方法来解决这个问题，因为我觉得我的解决方案真的很低效。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-04-22 19:47:15
想想哈希表是如何工作的。将哈希函数应用于项，并根据此哈希值将项分配给一个时隙。但可能会发生两个不同的项具有相同的散列值的情况。在这种情况下，哈希表将创建一个具有相同哈希值的列表。这叫做碰撞。
在哈希表实现中，我们试图避免冲突。但在这里它会为你服务的。如果您可以找到一个哈希函数:同一组中的两个数字具有相同的散列值，则可以轻松地将这些数字分组。
这类哈希函数的一个例子是：
- 将数字转换为字符串
- 按升序排序字符串
同一组中的所有数字都具有相同的散列值。
实例实现：
#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 : 3Stack Overflow用户
发布于 2016-04-22 18:34:39
所以，如果我正确理解这个问题，他们并不关心实际的数字。他们只是在问频率。因此，这将为我们提供一个std::map<int,int>，其中key是列表中的整数，value是该key中数字的频率。我们只需要将类别显示为任何值为1、2、3的东西。或者检查是否有相等的value等。
#include <iostream>
#include <vector>
#include <map>
int main()
{
std::vector<int> MyVec = { 1, 10, 3, 33 }; // sample data
std::map<int, int> MyMap;
for (int i = 0; i < MyVec.size(); i++) // fill the map with ALL the numbers first
MyMap[MyVec[i]]++;
for (auto itr = MyMap.begin(); itr != MyMap.end(); itr++) // increment each value based on the frequence of the digits found in the key
{
if (itr->first < 10) // it has one
continue;
else
{
int temp = itr->first;
while (temp >= 10)
{
temp = temp % 10;
itr->second++;
}
}
}
for (auto itr = MyMap.begin(); itr != MyMap.end(); itr++) // display
{
std::cout << "first: " << itr->first << " second: " << itr->second << "\n";
}
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36800585
复制相关文章
相似问题
腾讯云开发者
