在C ++中对O(1)额外空间中数组中所有元素的频率和O(n)时间进行计数

给定一个范围从值1到n的元素数组。有些元素是重复的，而有些则缺失。目的是找到O(n)时间和O(1)额外空间中所有元素的频率。

输入值

Arr[]= { 1,2,2,3,4,4,4,5 }

输出结果

1→ 1, 2 → 2, 3→ 1, 4→ 3, 5→ 5

说明-最高元素是5，输出显示每个元素出现在数组中的次数。

输入值

Arr[]= { 1,4,4,5,5,5,5 }

输出结果

1→ 1, 2 →0, 3→ 0, 4→ 2, 5→ 4

说明-最高元素是5，输出显示每个元素出现在数组中的次数。

以下程序中使用的方法如下

• 下面的程序适用于数字在1到10之间的数组。

• 函数printfrequency（int arr []，int n）将一个数组及其大小n作为输入，并返回数组中存在的1到10之间的数字计数。

• 我们使arr [i] = arr [i] -1使得每个索引都存储编号为i的频率，在索引0处存储的频率为1，依此类推。

• 在每个频率上使用for循环arr [arr [i]％10]将10添加到原始值。

• 对于x来说，如果数字i在数组中出现x次，则将添加10。

• 现在对索引i处的所有元素i + 1使用arr [i] / 10的for循环打印频率。

示例

#include<bits/stdc++.h>
using namespace std;
void printfrequency(int arr[],int n){
   int i=0;
   //1变为0，2变为1 ..... 10变为9，所以arr [i]的计数为i-
   for ( i =0; i<n; i++)
      arr[i] = arr[i]-1;
   //因为数字介于1到10之间，所以将所有数字加10（num％10是num本身）
   for (i=0; i<n; i++)
      arr[arr[i]%10] = arr[arr[i]%10] + 10;
   for (i =0; i<10; i++)
      cout << i + 1 << " -> " << arr[i]/10 << endl;
}
int main(){
   int arr[] = {2, 3, 3, 2, 5, 6, 7, 7, 7, 8, 8, 9, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   printfrequency(arr,n);
   return 0;
}

输出结果

1 -> 0
2 -> 2
3 -> 2
4 -> 0
5 -> 1
6 -> 1
7 -> 3
8 -> 2
9 -> 5
10 -> 0