Более элегантный способ проверить наличие дубликатов в массиве C ++?

Question

Я написал этот код на C ++ как часть универсальной задачи, в которой мне нужно убедиться, что в массиве нет дубликатов:

// 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

Это расширение к ответу @Puppy, который является наилучшим текущим ответом.

PS: я пытался вставить это сообщение как комментарий в текущем лучшем ответе @Puppy, но не смог, так как у меня еще нет 50 баллов. Также немного экспериментальных данных предоставлено здесь для дальнейшей помощи.

И std :: set, и std :: map реализованы в STL с использованием только сбалансированного дерева двоичного поиска. Так что оба приведут к сложности O (nlogn) только в этом случае. Хотя лучшая производительность может быть достигнута при использовании хеш-таблицы. std :: unordered_map предлагает реализацию на основе хеш-таблицы для более быстрого поиска. Я экспериментировал со всеми тремя реализациями и обнаружил, что результаты с использованием std :: unordered_map лучше, чем std :: set и std :: map. Результаты и код представлены ниже. Изображения - это снимок производительности, измеренный LeetCode в решениях.

</p> <pre><code>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 мс)

Набор / Карта Производительность

Answer 6

Я не уверен, почему это не было предложено, но в базе 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 7

Это нормально, особенно для небольших массивов.Я бы использовал более эффективные подходы (меньше n ^ 2/2 сравнений), если массив намного больше - см. Ответ DeadMG.

Некоторые небольшие исправления для вашего кода:

• Вместо int j = i напишите int j = i +1, и вы можете опустить свой if(j != i) test
• . Вам не нужно объявлять переменную i вне оператора for.

Answer 8

#include<iostream>
#include<algorithm>

int main(){

    int arr[] = {3, 2, 3, 4, 1, 5, 5, 5};
    int len = sizeof(arr) / sizeof(*arr); // Finding length of array

    std::sort(arr, arr+len);

    int unique_elements = std::unique(arr, arr+len) - arr;

    if(unique_elements == len) std::cout << "Duplicate number is not present here\n";
    else std::cout << "Duplicate number present in this array\n";

    return 0;
}

Answer 9

//std::unique(_copy) requires a sorted container.
std::sort(cont.begin(), cont.end());

//testing if cont has duplicates
std::unique(cont.begin(), cont.end()) != cont.end();

//getting a new container with no duplicates
std::unique_copy(cont.begin(), cont.end(), std::back_inserter(cont2));

Answer 10

Я думаю, что решение @Michael Jaison G действительно блестящее, я немного модифицирую его код, чтобы избежать сортировки (При использовании unordered_set алгоритм может немного ускориться.)

template <class Iterator>
bool isDuplicated(Iterator begin, Iterator end) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    std::unordered_set<T> values(begin, end);
    std::size_t size = std::distance(begin,end);
    return size != values.size();
}