c語言++數組名【數字】

Problem statement: Write a C++ program to print all the non-repeated numbers in an array in minimum time complexity.

問題陳述：編寫一個C ++程序， 以最小的時間復雜度將所有未重復的數字打印在數組中 。

Input Example:

輸入示例：

    Array length: 10
Array input: 2 5 3 2 4 5 3 6 7 3
Output:
Non-repeated numbers are: 7, 6, 4

Solution

解

Data structures used:

使用的數據結構：

    Unordered_map <int, int>

• Key in the map is array value

  映射中的鍵是數組值

• Value of key is frequency

  關鍵值是頻率

Algorithm:

算法：

1. Declare a map hash to store array elements as keys and to associate their frequencies with them.

   聲明地圖哈希，以將數組元素存儲為鍵并將其頻率與它們關聯。

2.     Unordered_map <int, int>hash;
   
   

3. For each array element

   對于每個數組元素

   Insert it as key & increase frequencies. (0 ->1)

   將其作為鍵插入并增加頻率。 (0-> 1)

   For same key it will only increase frequencies.

   對于相同的鍵，只會增加頻率。

4. For i=0: n-1
   hash[array [i]]++;
   End For
   
   

5. Now to print the non-repeated character we need to print the keys (array elements) having value (frequency) exactly 1. (Non-repeating)

   現在要打印非重復字符，我們需要打印值(頻率)正好為1的鍵(數組元素)。(非重復)

   Set an iterator to

   將迭代器設置為

   hash.begin().

   hash.begin() 。

   iterator->first is the key (array element) & iterator->second is the value( frequency of corresponding array value)

   iterator-> first是鍵(數組元素)＆ iterator-> second是值(對應數組值的頻率)

6. IF
   Iterator->second > 1
   Print iterator->first (the array element)
   END IF
   
   

Time complexity: O(n)

時間復雜度：O(n)

Explanation with example:

舉例說明：

For this array: 2 5 3 2 4 5 3 6 7 3

對于此陣列： 2 5 3 2 4 5 3 6 7 3

The code:

代碼：

for(int i=0;i<n;i++){//creating the map
hash[a[i]]++;//for same key increase frequency
}

Actually does the following

實際上是以下

    At i=0
array[i]=2
Insert 2 & increase frequency
Hash:
Key(element)	Value(frequency)
2	            1
At i=1
array[i]=5
Insert 5 & increase frequency
Hash:
Key(element)	Value(frequency)
2	            1
5	            1
At i=2
array[i]=3
Insert 3 & increase frequency
Hash:
Key(element)	Value(frequency)
2	            1
5	            1
3	            1
At i=3
array[i]=2
Insert 2 increase frequency
'2' is already there, thus frequency increase.
Hash:
Key(element)	Value(frequency)
2	            2
5	            1
3	            1
At i=4
array[i]=4
Insert 4 &increase frequency
Hash:
Key(element)	Value(frequency)
2	            2
5	            1
3	            1
4	            1
At i=5
array[i]=5
'5' is already there, thus frequency increase.
Hash:
Key(element)	Value(frequency)
2	            2
5	            2
3	            1
4	            1
At i=6
array[i]=3
'3' is already there, thus frequency increase.
Hash:
Key(element)	Value(frequency)
2	            2
5	            2
3	            2
4	            1
At i=7
array[i]=6
Insert 6, increase frequency.
Hash:
Key(element)	Value(frequency)
2	            2
5	            2
3	            2
4	            1
6	            1
At i=8
array[i]=7
Insert 7, increase frequency.
Hash:
Key(element)	Value(frequency)
2	            2
5	            2
3	            2
4	            1
6	            1
7	            1
At i=9
array[i]=3
'3' is already there, thus frequency increase.
Hash:
Key(element)	Value(frequency)
2	            2
5	            2
3	            3
4	            1
6	            1
7	            1

Thus, Elements with frequency 1 are: 7, 6, 4

因此，頻率為1的元素為：7、6、4

C ++實現可在數組中按頻率打印所有非重復數字 (C++ implementation to print all the Non-Repeated Numbers with Frequency in an Array)

#include <bits/stdc++.h>
using namespace std;
void findNonRepeat(int* a, int n){
//Declare the map
unordered_map<int,int> hash;
for(int i=0;i<n;i++){//creating the map
hash[a[i]]++;//for same key increase frequency
}
cout<<"the nonrepeating numbers are: ";
//iterator->first == key(element value)
//iterator->second == value(frequency)
for(auto it=hash.begin();it!=hash.end();it++)
if(it->second==1)//frequency==1 means non-repeating element
printf("%d ",it->first);
printf("\n");
}
int main()
{
int n;
cout<<"enter array length\n";
cin>>n;
int* a=(int*)(malloc(sizeof(int)*n));
cout<<"input array elements...\n";
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
//function to print repeating elements with their frequencies
findNonRepeat(a,n);
return 0;
}

Output

輸出量

enter array length
10
input array elements...
2 5 3 2 4 5 3 6 7 3
the nonrepeating numbers are: 7 6 4

翻譯自: https://www.includehelp.com/cpp-programs/print-all-the-non-repeated-numbers-in-an-array.aspx

c語言++數組名【數字】