配列内のすべての要素の頻度をO（1）の余分なスペースでカウントし、O（n）の時間をC++でカウントします

値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の頻度を格納し、1がインデックス0に格納されるようにします。

• 各周波数で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 becomes 0, 2 becomes 1 .....10 becomes 9 so arr[i] will have count of i
   for ( i =0; i<n; i++)
      arr[i] = arr[i]-1;
   //as numbers are between 1-10 add 10 to all (num%10 is num itself)
   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