更优雅的方法来检查C++数组中的重复项？

Question

我在C++中编写此代码作为uni任务的一部分,我需要确保数组中没有重复项:

// Check for duplicate numbers in user inputted data
    int i; // Need to declare i here so that it can be accessed by the 'inner' loop that starts on line 21
    for(i = 0;i < 6; i++) { // Check each other number in the array
        for(int j = i; j < 6; j++) { // Check the rest of the numbers
            if(j != i) { // Makes sure don't check number against itself
                if(userNumbers[i] == userNumbers[j]) {
                    b = true;
                }
            }
            if(b == true) { // If there is a duplicate, change that particular number
                cout << "Please re-enter number " << i + 1 << ". Duplicate numbers are not allowed:" << endl;
                cin >> userNumbers[i];
            }
        } // Comparison loop
        b = false; // Reset the boolean after each number entered has been checked
    } // Main check loop

它工作得很好,但我想知道是否有更优雅或有效的方法来检查.

Answer 1

您可以在O(nlog(n))中对数组进行排序,然后只需查看下一个数字即可.这比你的O(n ^ 2)现有算法要快得多.代码也更清洁.您的代码也不能确保在重新输入时不会插入重复项.您需要首先防止重复存在.

std::sort(userNumbers.begin(), userNumbers.end());
for(int i = 0; i < userNumbers.size() - 1; i++) {
    if (userNumbers[i] == userNumbers[i + 1]) {
        userNumbers.erase(userNumbers.begin() + i);
        i--;
    }
}

我也推荐使用std :: set - 在那里没有重复.

Answer 2

以下解决方案基于对数字进行排序,然后删除重复项:

#include <algorithm>

int main()
{
    int userNumbers[6];

    // ...

    int* end = userNumbers + 6;
    std::sort(userNumbers, end);
    bool containsDuplicates = (std::unique(userNumbers, end) != end);
}

Answer 3

事实上,最快和迄今为止我能看到的最优雅的方法如上所述:

std::vector<int> tUserNumbers;
// ...
std::set<int> tSet(tUserNumbers.begin(), tUserNumbers.end());
std::vector<int>(tSet.begin(), tSet.end()).swap(tUserNumbers);

它是O(n log n).但是,如果需要保留输入数组中数字的顺序,则不会这样做...在这种情况下,我做了:

    std::set<int> tTmp;
    std::vector<int>::iterator tNewEnd = 
        std::remove_if(tUserNumbers.begin(), tUserNumbers.end(), 
        [&tTmp] (int pNumber) -> bool {
            return (!tTmp.insert(pNumber).second);
    });
    tUserNumbers.erase(tNewEnd, tUserNumbers.end());

它仍然是O(n log n)并保持元素的原始排序tUserNumbers.

干杯,

保罗

Answer 4

您可以添加集合中的所有元素,并在添加时检查它是否已存在.那将更加优雅和高效.

Answer 5

我不确定为什么没有提出这个,但是这里有一种方法在10中找到O(n)中的重复项.我看到的已经建议的O(n)解决方案的问题是它需要数字首先排序..此方法是O(n),不需要对集进行排序.很酷的是检查特定数字是否有重复是O(1).我知道这个帖子可能已经死了,但也许它会帮助别人!:)

/*
============================
Foo
============================
* 
   Takes in a read only unsigned int. A table is created to store counters 
   for each digit. If any digit's counter is flipped higher than 1, function
   returns. For example, with 48778584:
    0   1   2   3   4   5   6   7   8   9
   [0] [0] [0] [0] [2] [1] [0] [2] [2] [0]

   When we iterate over this array, we find that 4 is duplicated and immediately
   return false.

*/
bool Foo( unsigned const int &number)
{
    int temp = number;
    int digitTable[10]={0};

    while(temp > 0)
    {
        digitTable[temp % 10]++; // Last digit's respective index.
        temp /= 10; // Move to next digit
    }

    for (int i=0; i < 10; i++)
    {
        if (digitTable [i] > 1)
        {
            return false;
        }
    }
    return true;
}

Answer 6

这是@Puppy的答案的延伸,这是目前最好的答案.

PS:我试图在@Puppy当前的最佳答案中插入这篇文章作为评论,但不能这样,因为我还没有50分.此处还分享了一些实验数据以获得进一步的帮助.

std :: set和std :: map都是在STL中使用Balanced Binary Search树实现的.因此,只有在这种情况下,两者都会导致O(nlogn)的复杂性.如果使用哈希表,则可以实现更好的性能.std :: unordered_map提供基于哈希表的实现,以加快搜索速度.我尝试了所有三个实现,并发现使用std :: unordered_map的结果比std :: set和std :: map更好.结果和代码在下面分享.图像是LeetCode在解决方案上测量的性能快照.

bool hasDuplicate(vector<int>& nums) {
    size_t count = nums.size();
    if (!count)
        return false;
    std::unordered_map<int, int> tbl;
    //std::set<int> tbl;
    for (size_t i = 0; i < count; i++) {
        if (tbl.find(nums[i]) != tbl.end())
            return true;
        tbl[nums[i]] = 1;
        //tbl.insert(nums[i]);
    }
    return false;
}

unordered_map性能(此处运行时间为52毫秒)

设置/映射性能