Как найти единственное число в массиве, который не встречается дважды

Ответ 1

Вы можете определить целочисленный "результат", инициализированный на 0, а затем вы выполняете некоторые побитовые операции, применяя логику XOR ко всем элементам вашего массива.

В конце "результат" будет равен единственному элементу, который появляется только один раз.

result = 0
for i in array:
  result ^= i
return result

http://en.wikipedia.org/wiki/Bitwise_operation#XOR

Например, если ваш массив содержит элементы [3, 4, 5, 3, 4], алгоритм вернет

3 ^ 4 ^ 5 ^ 3 ^ 4

Но оператор XOR ^ ассоциативен и коммутативен, поэтому результат будет также равен:

(3 ^ 3) ^ (4 ^ 4) ^ 5

Так как я ^ я = 0 для любого целого числа я и я ^ 0 = i, вы имеете

(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5

Ответ 2

Я уже видел этот вопрос. Это трюк. Предполагая, что все повторяющиеся числа отображаются ровно дважды, вы делаете это:

int result = 0;
for (int a : arr)
    result ^= a;

Ответ 3

Еще одно "обычное" решение (на Java):

public static int findSingle(int[] array) {

    Set<Integer> set = new HashSet<Integer>();

    for (int item : array) {
        if (!set.remove(item)) {
            set.add(item);
        }
    }       

    assert set.size() == 1;

    return set.iterator().next();
}

На мой взгляд, решение с XOR выглядит красиво.

Это не так быстро, как XOR, но использование HashSet делает его близким к O (n). И это, безусловно, более читаемо.

Ответ 4

Лучший ответ уже дан (XOR-ing), это будет альтернативный, более общий способ.

Если входной массив будет отсортирован (мы можем его отсортировать), мы могли бы просто перебирать элементы в парах (шаг за шагом 2), а если элементы "пары" различны, мы делаем следующее:

public static int findSingle(int[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i] != arr[i + 1])
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

Примечание.. Это решение сортирует входной массив; если это нежелательно или не разрешено, он может быть клонирован первым:

arr = arr.clone();

Если входной массив отсортирован, вызов Arrays.sort(arr) может быть оставлен, конечно.

Обобщение

Преимущество этого решения заключается в том, что его можно применять ко всем типам, которые сопоставимы и поэтому могут быть отсортированы (типы, которые реализуют Comparable), например String или Date, Решение XOR ограничено только цифрами.

Вот немного модифицированная версия, которая берет входной массив любого типа элемента, который сопоставим:

public static <E extends Comparable<E>> E findSingle(E[] arr) {
    Arrays.sort(arr);
    for (int i = 0, max = arr.length - 1; i < max; i += 2)
        if (arr[i].compareTo(arr[i + 1]) != 0)
            return arr[i];
    return arr[arr.length - 1]; // Single element is the last
}

Примечание. В большинстве случаев вы также можете использовать arr[i].equals(arr[i + 1]) для сравнения элементов вместо Comparable.compareTo(). Подробнее читайте связанный javadoc. Цитирование соответствующей части:

Настоятельно рекомендуется, но не обязательно, чтобы (x.compareTo(y)==0) == (x.equals(y)). Вообще говоря, любой класс, реализующий интерфейс Comparable и нарушающий это условие, должен четко указывать этот факт. Рекомендуемый язык: "Примечание: этот класс имеет естественный порядок, который несовместим с равными".

Теперь вы можете вызвать это с помощью String[], например:

System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));

Вывод:

2

Заключительные примечания:

Начиная с оператора проблемы, он не проверяется, есть ли более двух вхождений элементов, и не является ли длина массива нечетной. Кроме того, второй пример не проверяет значения null, они должны быть добавлены, если необходимо.

Ответ 5

Здесь немного менее запутанный способ сделать это:

List list = Arrays.asList(a);
int result;
for(int i:a)
{
    if(list.indexOf(i)==list.lastIndexOf(i))
    {
        result = i;
        break;
    }
}

result будет содержать не повторяющееся значение.