[已解决]为什么一直输出的是错的答案

wwWsir

给定一个长度为 n的数组 a，请你编写一个函数：

int get_unique_count(int a[], int n);  // 返回数组前n个数中的不同数的个数
输入格式
第一行包含一个整数 n

第二行包含 n 个整数，表示数组 a
输出格式
共一行，包含一个整数表示数组中不同数的个数。
数据范围
1≤n≤1000
,
1≤ai≤1000
。
代码思路：想先找出一样的值，再用总数量减去相同数量求出不同的个数

1. #include<iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int getcount(int a[], int n);
   
6. int main()
   
7. {
   
8.     int n;
   
9.     cin>>n;
   
10.     int a[1000];
    
11.     for(int i=0; i<n; i++) cin>>a[i];
    
12.     getcount(a, n);
    
13. }
    
14. 
    
15. int getcount(int a[], int n)
    
16. {
    
17.     int count=0;
    
18.     for(int i=0; i<n; i++)
    
19.     {
    
20.         for(int j=1; j<n; j++)
    
21.         {
    
22.             if(a[i] == a[j])
    
23.             {
    
24.                
    
25.                 count++;
    
26.                 break;
    
27.             }
    
28.         }
    
29.     }
    
30.     cout<<n - count;
    
31. }
    

复制代码

最佳答案

月排行榜 / 总排行榜

isdkz

2023-7-20 01:21:58

代码中存在一个关键问题：在检查数组中重复元素的过程中，它不仅会检查后续元素与当前元素是否相等，也会检查先前已经检查过的元素。这就导致了一些元素被多次计数，结果就可能不准确。

为了修复这个问题，我们需要修改内层循环，让它只检查当前元素后面的元素，而不是所有元素。可以通过让 j 从 i+1 开始，而不是从1开始来实现。

修复后的代码如下：

1. #include<iostream>
2. using namespace std;
4. int get_unique_count(int a[], int n);
6. int main()
7. {
8.     int n;
9.     cin>>n;
10.     int a[1000];
11.     for(int i=0; i<n; i++) cin>>a[ i];
12.     cout << get_unique_count(a, n);
13. }
15. int get_unique_count(int a[], int n)
16. {
17.     int count = 0;
18.     for(int i=0; i<n; i++)
19.     {
20.         for(int j=i+1; j<n; j++)
21.         {
22.             if(a[ i] == a[j])
23.             {
24.                 count++;
25.                 break;
26.             }
27.         }
28.     }
29.     return n - count;
30. }

复制代码

然而，这个函数还是有问题的，因为它只在找到第一个匹配的时候就停止搜索，而忽略了可能存在的其他匹配。实际上，这个函数计算的是数组中有多少个元素至少有一个重复。

如果我们想要计算数组中不同的元素的个数，一个更好的方法是使用集合（set）来存储已经看到的元素。集合的特性就是它会自动去除重复的元素。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

这是使用C++标准库中的集合来解决这个问题的代码：

1. #include<iostream>
2. #include<set>
3. using namespace std;
5. int get_unique_count(int a[], int n);
7. int main()
8. {
9.     int n;
10.     cin>>n;
11.     int a[1000];
12.     for(int i=0; i<n; i++) cin>>a[ i];
13.     cout << get_unique_count(a, n);
14. }
16. int get_unique_count(int a[], int n)
17. {
18.     set<int> s;
19.     for(int i=0; i<n; i++)
20.     {
21.         s.insert(a[ i]);
22.     }
23.     return s.size();
24. }

复制代码

这个版本的 get_unique_count 函数将数组中的每个元素插入到一个集合中，然后返回集合的大小，即不同元素的数量。因为集合自动忽略重复的插入，所以这个函数能正确地计算出不同元素的数量。

跳转到最佳答案楼层

Mike_python小

【求助帖】请及时确认最佳答案，下次提问时可以得到更多关注，问题可以更快解决

以下是对给定代码的一些修改建议和解释：

1. 
   
2. #include <iostream>
   
3. #include <unordered_set>  // 使用无序集合来存储不同的数
   
4. using namespace std;
   
5. 
   
6. int get_unique_count(int a[], int n);
   
7. 
   
8. int main() {
   
9.     int n;
   
10.     cin >> n;
    
11.    
    
12.     int a[1000];
    
13.     for (int i = 0; i < n; i++)
    
14.         cin >> a[i];
    
15.    
    
16.     cout << get_unique_count(a, n) << endl;
    
17.    
    
18.     return 0;
    
19. }
    
20. 
    
21. int get_unique_count(int a[], int n) {
    
22.     unordered_set<int> unique_nums;  // 存储不同的数
    
23.    
    
24.     for (int i = 0; i < n; i++) {
    
25.         unique_nums.insert(a[i]);  // 将数组元素插入到集合中
    
26.     }
    
27.    
    
28.     return unique_nums.size();  // 返回集合中不同数的个数
    
29. }
    

复制代码

代码修改解释：
引入<unordered_set>头文件，使用了无序集合unordered_set来存储不同的数。
在get_unique_count函数中，通过循环将数组中的元素插入到无序集合中。
最后，返回无序集合的大小，即可得到数组中不同数的个数。

希望以上解答对你有帮助！如果还有其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

代码中存在一个关键问题：在检查数组中重复元素的过程中，它不仅会检查后续元素与当前元素是否相等，也会检查先前已经检查过的元素。这就导致了一些元素被多次计数，结果就可能不准确。

为了修复这个问题，我们需要修改内层循环，让它只检查当前元素后面的元素，而不是所有元素。可以通过让 j 从 i+1 开始，而不是从1开始来实现。

修复后的代码如下：

1. #include<iostream>
2. using namespace std;
4. int get_unique_count(int a[], int n);
6. int main()
7. {
8.     int n;
9.     cin>>n;
10.     int a[1000];
11.     for(int i=0; i<n; i++) cin>>a[ i];
12.     cout << get_unique_count(a, n);
13. }
15. int get_unique_count(int a[], int n)
16. {
17.     int count = 0;
18.     for(int i=0; i<n; i++)
19.     {
20.         for(int j=i+1; j<n; j++)
21.         {
22.             if(a[ i] == a[j])
23.             {
24.                 count++;
25.                 break;
26.             }
27.         }
28.     }
29.     return n - count;
30. }

复制代码

然而，这个函数还是有问题的，因为它只在找到第一个匹配的时候就停止搜索，而忽略了可能存在的其他匹配。实际上，这个函数计算的是数组中有多少个元素至少有一个重复。

如果我们想要计算数组中不同的元素的个数，一个更好的方法是使用集合（set）来存储已经看到的元素。集合的特性就是它会自动去除重复的元素。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

这是使用C++标准库中的集合来解决这个问题的代码：

1. #include<iostream>
2. #include<set>
3. using namespace std;
5. int get_unique_count(int a[], int n);
7. int main()
8. {
9.     int n;
10.     cin>>n;
11.     int a[1000];
12.     for(int i=0; i<n; i++) cin>>a[ i];
13.     cout << get_unique_count(a, n);
14. }
16. int get_unique_count(int a[], int n)
17. {
18.     set<int> s;
19.     for(int i=0; i<n; i++)
20.     {
21.         s.insert(a[ i]);
22.     }
23.     return s.size();
24. }

复制代码

这个版本的 get_unique_count 函数将数组中的每个元素插入到一个集合中，然后返回集合的大小，即不同元素的数量。因为集合自动忽略重复的插入，所以这个函数能正确地计算出不同元素的数量。