计数数组中项目的频率-没有两个for循环

Question

需要知道是否有一种方法可以在不使用两个循环的情况下计算数组中项目的频率。这是在不知道数组大小的情况下。如果我知道数组的大小，我可以使用switch而不用循环。但我需要更多才多艺的人。我认为修改快速排序可能会得到更好的结果。

Array[n];
TwoDArray[n][2];

第一个循环将遍历Array[]，而第二个循环将查找元素并在二维数组中增加其计数。

max = 0;
for(int i=0;i<Array.length;i++){
found= false;
for(int j=0;j<TwoDArray[max].length;j++){
if(TwoDArray[j][0]==Array[i]){
TwoDArray[j][1]+=;
found = true;
break;
}
}
if(found==false){
TwoDArray[max+1][0]=Array[i];
TwoDArray[max+1][1]=1;
max+=;
}

如果你能评论或提供更好的解决方案将非常有帮助。

Answer 1

使用map或哈希表来实现。插入key作为数组项，value作为频率。

如果数组元素的范围不是太大，也可以使用

。

Answer 2

我将构建一个以数组中的项目为键的映射，并使用该项目的计数作为值。一次遍历数组以构建包含计数的映射。对于每个项目，在映射中查找其计数，增加计数，并将新计数放回映射中。

map的put和get操作可以是常数时间(例如，如果您使用具有良好哈希函数和适当大小的后备存储的哈希映射实现)。这意味着你可以计算出与数组中元素数量成正比的频率。

Answer 3

我并不是说这比使用map或哈希表更好(特别是在有很多重复项的情况下，尽管在这种情况下，您可以使用某些技术接近O(n)排序，所以这也不是太糟糕)，它只是一种替代方法。

• 排序

• 使用(单个)for循环遍历排序数组

  • 如果找到与前一个相同的元素，则增加当前计数

  • 如果你找到一个不同的元素，存储前一个元素和它的计数，并设置计数为1

  • 在循环结束时，存储前一个元素及其计数