在数组中查找唯一数字 [英] Find unique numbers in array

问题描述

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

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

例如，如果数组为:1 9 4 5 8 3 1 3 5

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

输出应该为6，因为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).

所以，到目前为止，这是我的代码.

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

推荐答案

让我加入聚会;)

您还可以使用哈希表:

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

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

• 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::bitset instead, 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>.

这篇关于在数组中查找唯一数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！