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

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

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

еще одно "обычное" решение (на 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). И это, конечно, более читабельно.

лучший ответ уже дан (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(). Дополнительные сведения см. В связанной документации. Цитируя соответствующую часть:

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

теперь вы можете называть это String[] например:

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

выход:

2

конечные ноты:

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

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

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

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