在数组中找到唯一的数字

Question

好的，我需要找出一个数组中有多少个不同的数字。

例如，如果数组是：1 9 4 5 8 3 1 3 5

输出应该是6，因为1、9、4、5、8、3是唯一的，而1、3、5是重复的（不唯一）。

以下是我目前的代码..... 不起作用。

#include <iostream>

using namespace std;

int main() {
    int r = 0, a[50], n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < j; k++) {
            if (a[k] != a[j]) r++;
        }
    }
    cout << r << endl;
    return 0;
}

- user2041143

---

对数组进行排序，然后问题就变得微不足道了。尝试自己想一下，这种复杂度与你的解决方案相比如何。 - Kerrek SB

这对我来说似乎是作业...但是，你可以对数组进行排序，或者你可以使用哈希表。 - Reinderien

似乎SO是一个很好的地方来完成最后一分钟的家庭作业。将问题格式化并发布在SO上，然后等待答案即可！ - thang

@thang：看起来不是这样的——因为几乎所有对这个问题的回答都有错误的算法或使用标准库来完成任务——显然这不是这个作业要求的内容... - JoergB

这是我发现的最好的逻辑。https://dev59.com/tl4c5IYBdhLWcg3wFm84 - Rasmi Ranjan Nayak

Answer 1

让我也加入这个派对吧 ;)

你也可以使用哈希表：

#include <unordered_set>
#include <iostream>

int main() {

    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };
    const size_t len = sizeof(a) / sizeof(a[0]);

    std::unordered_set<int> s(a, a + len);

    std::cout << s.size() << std::endl;
    return EXIT_SUCCESS;

}

虽然这里并不重要，但是对于大数组来说，这可能会有最佳表现。

---

如果最大值和最小值之间的差异相当小，则可以做得更快：

• 创建一个 vector<bool> ，跨越最小元素和最大元素之间的范围（如果您在编译时知道数组元素，则建议使用 std::bitset ，但是您可以使用模板元编程在编译时计算所有东西）。
• 对于输入数组的每个元素，在 vector<bool> 中设置相应的标志。
• 完成后，只需计算 vector<bool> 中的 true 的数量即可。

- Branko Dimitrijevic

---

谢谢你的帮助，虽然这不是很基础，但我很感激你的帮助。 - user2041143

Answer 2

std::set 包含的元素已经是唯一的。

#include <set>

int main()
{
    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };

    std::set<int> sa(a, a + 9);
    std::cout << sa.size() << std::endl;
}

- dreamlax

---

“9”是指条目数量还是最高值？ - Ben

@Ben 不是的，它是一个数组的大小。 - udit043

Answer 3

这个怎么样？

#include <list>

int main()
{
    int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5};

    std::list<int> la(a, a+9);
    la.sort();
    la.unique();
    std::cout << la.size() << std::endl;

    return 0;
}

- billz

---

你也可以使用 std::set :P - Rapptz

我的问题是我还没有学过向量，而且我必须只使用循环/数组来完成这个。能帮帮我吗？ - user2041143

你需要先对它进行排序，然后计算相邻元素。 - billz

la.unique()方法的正确性是否取决于首先运行sort()方法？ - Nicholas Hamilton

Answer 4

既然您已经说明不能使用标准库，必须使用循环，那么我们尝试这个解决方案。

#include <iostream>

using namespace std; // you're a bad, bad boy!

int main() 
{
    int r = 0, a[50], n;

    cout << "How many numbers will you input? ";
    cin >> n;

    if(n <= 0)
    {
        cout << "What? Put me in Coach. I'm ready! I can do this!" << endl;
        return -1;
    }

    if(n > 50)
    {
        cout << "So many numbers! I... can't do this Coach!" << endl;
        return -1;
    }   

    cout << "OK... Enter your numbers now." << endl;

    for (int i = 0; i < n; i++)
        cin >> a[i];


    cout << "Let's see... ";

    // We could sort the list but that's a bit too much. We will choose the
    // naive approach which is O(n^2), but that's OK. We're still learning!

    for (int i = 0; i != n; i++) 
    { // Go through the list once.      
        for (int j = 0; j != i; j++)
        { // And check if this number has already appeared in the list:
            if((i != j) && (a[j] == a[i]))
            { // A duplicate number!        
                r++; 
                break;
            }
        }
    }

    cout << "I count " << n - r << " unique numbers!" << endl;

    return 0;
}

我强烈建议你不要把这段代码作为你的作业提交——至少在理解它之前不要这么做。这只会对自己造成损失，而且很可能你的教师也会知道你根本没有编写它：我以前也是一个作业评分者，当某人的代码质量奇迹般提高时，很明显能感觉到。

- Nik Bougalis

---

这解决了一个不同的问题：它计算仅出现一次而不是所有不同值的数量。 - JoergB

@joergb 你错了。再读一遍代码 - 告诉我 n - r 计算的是什么。真的不难弄清楚；如果必须，你甚至可以运行代码。 - Nik Bougalis

我再次阅读了代码，甚至对照 OP 的测试输入运行了一遍：对于该输入，它返回 3，而不是指定问题的 6。正如我所说的那样：你的代码计算仅出现一次的数字。r 计算所有重复出现的数字 - 即使是第一个。OP 想要计算 所有 不同数字的数量。使用 std::set 或 std::list 的解决方案可以得到正确的结果。 - JoergB

哦，哇，你是对的。我完全误读了问题。会调整代码。 - Nik Bougalis

Answer 5

请对您的代码进行干扰测试。在外部循环中，每个元素都会在内部循环中被计算多次。假设循环包含1、2、3、4.1.....元素，请在第二次迭代和第三次迭代中对其进行干扰测试。1被计算了两次，因为1既不等于2也不等于3。

现在是解决问题的时候了！

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
ll arr[1000007]={0};
int main()
{
  ios_base::sync_with_stdio(false);//used for fast i/o
    ll n;cin>>n;
      for(ll i=1;i<=n;i++)
        cin>>arr[i];

        sort(arr,arr+n);

       ll cnt=0;
                for(ll i=1;i<=n-1;i++)
                  {
                   if(arr[i+1]-arr[i]==0)
                     cnt++;
                  }
                 cout<<n-cnt<<endl;


  cin.tie(NULL);
  return 0;
}

- Sourabh

Answer 6

我认为增加 r 值的位置不正确

#include <iostream>
using namespace std;

int main()
{
    int r=0,a[50],n;
    cin >>n;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    for (int j=0;j<n;j++)
    {   
        bool flag = true;  
        for(int k=;k<j;k++)
        {
            if(a[k]!=a[j])
            {
               flag = false;
               break;
            }
       }
       if (true == flag) 
       {
           r++;
       }
    }
    cout << r << endl;
    return 0;
}

然而，我的建议是使用更复杂的算法（这个算法的时间复杂度为O(N^2)）。

- iampat

---

O(n^2)的复杂度 和 if (true == flag)？后者尤其让人感到恐惧。 - dreamlax

不，我的意思是，你不能想出为什么它没有按预期工作吗？ - Nik Bougalis

不是很清楚，特别是在布尔值方面，我更加困惑了。 - user2041143

问题不在于布尔值，而在于主要条件中。如果你把“flag”重命名为一个能够表达其含义的名称，你或许就能发现问题所在了。 - JoergB

Answer 7

这应该可以工作，但可能不是最优解决方案。

#include <iostream>

using namespace std;

int main()
{
int a[50],n;        
int uniqueNumbers; // this will be the total numbers entered and we will -- it
cin >>n;    
uniqueNumbers = n;  
for(int i=0;i<n;i++)
{
    cin >> a[i];
}   
for (int j=0;j<n;j++)
{   
    for(int k=0;k<n;k++)
    {
        /* 
        the and clause below is what I think you were missing.
        you were probably getting false positatives when j == k because a[1] will always == a[1] ;-)
        */
        if((a[k] == a[j]) && (k!=j)) 
        { uniqueNumebers--; }
    }       
}
cout << uniqueNumbers << endl;
return 0;
}

- cameronjchurch

Answer 8

我们可以在这个程序中使用C++ STL向量。

  int main() 
  {
    int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5};
    vector<int>v(a, a+9);

    sort(v.begin(), v.end()); 
    v.erase(unique(v.begin(), v.end()), v.end()); 

    cout<<v.size()<<endl;

    return 0;
  }

- rashedcs

Answer 9

虽然不如使用 set 那样优雅，但速度快了 1.4 倍

int a[] = {1, 9, 4, 5, 8, 3, 1, 3, 5}

std::map<int, char> m;

for (int i = 0; i < 9; i++) {
    if ( m.count(a[i]) == 0 )
        m.insert( pair<int, char>(a[i], 0x00) );
}

Map中的键m表示数组a中唯一值的列表

- Alexander Zyuzin

Answer 10

#include<bits/stdc++.h> using namespace std;

# 包含 <bits/stdc++.h> 头文件 使用命名空间 std

int find_unique(int arr[], int size){

    int ans = 0;
    for(int i = 0; i < size; i++){
        ans = ans^arr[i];  // this is bitwise operator .its call XOR  it's return only unique value..  

    }

    return ans;
}

void print_array(int arr[], int size){
    
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);  // use for fast input and output....

    int arr[5] = {1, 3, 5, 3, 1};

    cout <<"Orginal array: " << endl;
    print_array(arr, 5);
    int result = find_unique(arr, 5);
    cout << result << endl;

    return 0;
}

- MD. Anisul Islam