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

Ответ 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 - нет дубликатов там.

Ответ 2

Следующее решение основано на сортировке чисел и последующем удалении дубликатов:

#include <algorithm>

int main()
{
    int userNumbers[6];

    // ...

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

Ответ 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.

Приветствия,

Пол

Ответ 4

Вы можете добавить все элементы в набор и проверить при добавлении, если он уже присутствует или нет. Это было бы более элегантно и эффективно.

Ответ 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 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 respective index.
        temp /= 10; // Move to next digit
    }

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

Ответ 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 мс)

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

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

Как упомянуто @underscore_d, элегантное и эффективное решение будет

#include <algorithm>
#include <vector>

template <class Iterator>
bool has_duplicates(Iterator begin, Iterator end) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    std::vector<T> values(begin, end);

    std::sort(values.begin(), values.end());
    return (std::adjacent_find(values.begin(), values.end()) != values.end());
}

int main() {
    int user_ids[6];
    // ...
    std::cout << has_duplicates(user_ids, user_ids + 6) << std::endl;
}

Ответ 11

Я думаю, что решение @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();
}