Каков эффективный алгоритм для поиска одного уникального числа в наборе из 1 миллиона чисел?

Ответ 1

Используйте xor для всех номеров последовательно.

Для следующего списка чисел:

1, 2, 3, 4, 3, 2, 1

Пусть ^ представляет собой исключительную дизъюнкцию (или xor)

Затем,
1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 2 ^ 1 = 4

Ответ 2

попробуйте это

    int[] a = {1, 2, 1, 2, 3};
    Arrays.sort(a);
    for(int i = 0; i < a.length; i++) {
        if (i == 0 && a[i] != a[i + 1] || i == a.length -1 || a[i] != a[i - 1] && a[i] != a[i + 1]) {
            System.out.println(a[i]);
            break;
        }
    }

Ответ 3

Еще одно простое решение: можно использовать два бита, один для обозначения существования числа и другого, чтобы отметить дублирование. Мы итерации через массив amd отмечаем каждый элемент для существования и дублирования. Затем мы перебираем биты, чтобы найти число, которое помечено для существования, но не помечено для дублирования.

int[] numbers = new int[] { 1, 1, 2, 2, 3, 4, 4, 5, 5 };

    BitSet bs1 = new BitSet();
    BitSet bs2 = new BitSet();

    int largestNumber = 0;

    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];
        if (bs1.get(number) == false) {
            // Mark for existence
            bs1.set(number);
        } else {
            // Mark for duplicating
            bs2.set(number);
        }

        if (number > largestNumber) {
            largestNumber = number;
        }
    }

    for (int i = 0; i <= largestNumber; i++) {
        if (bs1.get(i) && !bs2.get(i)) {
            System.out.println("Non duplicating number is:  " + i);
        }
    }

}

Ответ 4

Ниже приведена проблема:

Сложность: O(N)

// Assuming the duplicate are going by pair
// x ^x == 0 and x ^0 == x
int find_unique(const std::vector<int>& v)
{
    assert(v.size() % 2 == 1);

    int res = 0;
    for (auto value : v) {
        res ^= value;
    }
    return res;
}

Или
Сложность: O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    if (it == v.begin()) { throw std::runtime_error("no unique number"); }
    if (it != v.begin() + 1) { throw std::runtime_error("several unique numbers"); }
    return v[0];
}

или Сложность: O(N log N)

int find_unique(std::vector<int>& v)
{
    if (v.empty()) { throw std::runtime_error("empty vector"); }
    if (v.size() == 1) { return v[0]; }
    std::sort(v.begin(), v.end());
    if (v[0] != v[1]) { return v[0]; }

    for (int i = 1, size = v.size(); i + 1 < size; ++i) {
        if (v[i] == v[i - 1]) { continue; }
        if (v[i] == v[i + 1]) { ++i; continue; } // we may skip v[i + 1]
        return v[i];
    }
    return v.back();
}

Ответ 5

Я считаю, что если мы объединим технологию quicksort (search) и xor, мы сможем получить самый быстрый код. Я пытаюсь, хотя, но исправьте меня, если эта идея не так тем временем.

Кстати, у этого есть большое количество usecases. Хотя вопрос является агностиком языка и требует четкого алгоритма, я упоминаю некоторые примеры использования, которые читатели могут найти полезными.

0 может быть дублирующимся... или отрицательным числом...

System.out.println(33 ^ 33 ^ 7 ^ 0 ^ 0 ^ 5 ^ 7 ^ 5); дает 0 (0 здесь является дубликатом)

Дубликаты могут быть больше 2:

System.out.println(1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 3); дает 1 вместо 2...

И снова и снова вопрос может быть сложным, чем мы могли бы сначала подумать.

Ответ 6

Для большого количества входных элементов (в отличие от примеров с несколькими номерами) требуется значительное количество времени, чтобы получить вход в некоторую структуру данных. Я думал об использовании этого необходимого времени как части процесса вычисления, помещая его в карту. Значение карты будет только для одного единственного числа. Я предполагаю, что данные верны, поэтому я опускаю проверку на это, но если есть несколько чисел, которые происходят только один раз, он просто вернет первый.

Должно быть место для дальнейшей оптимизации, например. путем доступа к карте по значению и просто найдите ту, которая имеет 1. Я думаю, что это можно сделать легко с помощью Boost.Bimap.

int getSingleNumber(){

map<int, int> numbers;

for (all input items)
    {
    numbers[currentInputItem]++;
    }

for( map<int,int>::iterator ii=numbers.begin(); ii!=numbers.end(); ++ii)
{
    if ( (*ii).second == 1 ) return (*ii).first;
}
}