C++ 在数组中查找唯一数字

Find unique numbers in array

提问by user2041143

Well, I have to find how many different numbers are in an array.

好吧，我必须找出数组中有多少个不同的数字。

For example if array is: 1 9 4 5 8 3 1 3 5

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

The output should be 6, because 1,9,4,5,8,3 are unique and 1,3,5 are repeating (not unique).

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

So, here is my code so far..... not working properly thought.

所以，到目前为止，这是我的代码......没有正常工作。

#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;
}

回答by Branko Dimitrijevic

Let me join the party ;)

让我加入派对;)

You could also use a hash-table:

您还可以使用哈希表：

#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;

}

Not that it matters here, but this will likely have the best performance for large arrays.

这并不重要，但这可能对大型阵列具有最佳性能。

---

---

If the difference between smallest and greatest element is reasonably small, then you could do something even faster:

如果最小元素和最大元素之间的差异相当小，那么您可以更快地做一些事情：

• Create a vector<bool>that spans the range between min and max element (if you knew the array elements at compile-time, I'd suggest the std::bitsetinstead, but then you could just compute everything in the compile-time using template meta-programming anyway).
• For each element of the input array, set the corresponding flag in vector<bool>.
• Once you are done, simply count the number of trues in the vector<bool>.

• 创建一个vector<bool>跨越 min 和 max 元素之间的范围（如果您在编译时知道数组元素，我建议std::bitset改为，但无论如何您都可以使用模板元编程在编译时计算所有内容）。
• 对于输入数组的每个元素，在 中设置相应的标志vector<bool>。
• 完成后，只需计算 .s 文件中trues的数量vector<bool>。

回答by dreamlax

A std::setcontains only unique elements already.

Astd::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;
}

回答by billz

How about this?

这个怎么样？

#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;
}

回答by Nik Bougalis

Since you've stated that you cannot use the standard library and must use loops, let's try this solution instead.

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

#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;
}

I urgeyou to notsubmit this code as your homework - at least not without understanding it. You will only do yourself a disservice, and chances are that your instructor will know that you didn't write it anyways: I've been a grader before, and it's fairly obvious when someone's code quality magically improves.

我敦促您不要将此代码作为作业提交 - 至少在没有理解它的情况下。你只会对你自己造成伤害，而且很有可能你的导师会知道你没有写它：我以前做过评分员，当某人的代码质量神奇地提高时，这是相当明显的。

回答by rashedcs

We can use C++ STL vector in this program .

我们可以在这个程序中使用 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;
  }

回答by Sourabh

Please dry run your code See in the outer for loop for each element it is counted more than one inside inner loop.let us say the loop contains 1,2,3,4.1.....elements dry run it in the second iteration and third iteration 1 is counted because 1 is 1!=2 as well as 1!=3

请干运行您的代码 在外部 for 循环中查看每个元素在内部循环中计数不止一个。假设循环包含 1,2,3,4.1 ..... 元素在第二次迭代中干运行它第三次迭代 1 被计算在内，因为 1 是 1!=2 以及 1!=3

Now solution time!!

现在解决时间！！

#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;
}

回答by cameronjchurch

this should work, however its probably not the optimum solution.

这应该有效，但它可能不是最佳解决方案。

#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;
}

回答by iampat

I think the location for increasing the value of r is incorrect

我认为增加 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;
}

However, my suggestion is using more sophisticated algorithms (this algorithm has O(N^2)).

但是，我的建议是使用更复杂的算法（该算法有 O(N^2)）。