XOR для поиска дубликатов в массиве

Я видел решение этой проблемы в этой теме → Как найти повторяющийся элемент в массиве перемешанных последовательных целых чисел?

Но проблема, с которой я сейчас сталкиваюсь, мало чем отличается от нее.

int arr[10] = {1,2,3,4,5,6,7,8,4,9};
    int a= 0;
    for(int i=0;i<10;i++) {
     a= a^ arr[i] ^i;
    }
    cout<<a;

Рассмотрим приведенный выше фрагмент кода. Вещи работают нормально, как есть. Но когда я добавляю 0 к вышеупомянутому массиву, например, int arr[11] = {0,1,2,3,4,5,6,7,8,4,9};, я не получаю правильный повторяющийся элемент. Может ли кто-нибудь исправить мою ошибку, которую я здесь делаю?


c++ algorithm xor
person Ajai    schedule 05.11.2011    source источник
comment
Вы забыли изменить цикл for? i<11 вместо i<10? Две самые сложные проблемы в CS: присвоение имен вещам, инвалидация кеша и ошибки «один за другим».   -  person krousey    schedule 05.11.2011

Ответы (3)


arrow_upward
3
arrow_downward

Трюк основан на значениях от 1 до n. Если числа находятся в каком-то другом диапазоне, вам придется их компенсировать.

static const int n = 11;
int arr[n] = {0,1,2,3,4,5,6,7,8,4,9};
int offset = 1;
int a= 0;
for(int i=0;i<n;i++) {
 a= a^ (arr[i]+offset) ^i;
}
cout<< (a-offset);
person Vaughn Cato    schedule 05.11.2011
comment
Мне жаль, что я только что проверил это с помощью нескольких других входных данных, и я думаю, что решение нужно немного изменить. Этот код будет работать нормально, если элементы отсортированы. Что, если это не так? Это не сработало для ввода ниже, int arr[20] = {0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16 ,18,17,14}; инт смещение = 1; инт а = 0; for(int i=0;i‹20;i++) { a= a^ (arr[i]+offset) ^i; } cout‹‹ (a-смещение); - person Ajai; 05.11.2011
comment
Размер вашего массива равен 20, но у вас есть i‹11. - person Vaughn Cato; 05.11.2011
comment
Я ужасно сожалею о такой ошибке. Да, ваше решение работает нормально. - person Ajai; 05.11.2011

arrow_upward
1
arrow_downward

Я предполагаю, что это может быть связано с тем фактом, что значение i будет таким же, как arr[i]

это как делать:

00000001 ^ 00000001

что равно 00000000

и я могу думать неправильно, но не испортит ли это процесс?

person DanZimm    schedule 05.11.2011
comment
Да, я заметил это и даже вручную записывал вывод на каждой итерации, и 0 в массиве — единственное, что делает эту проблему странной. Я не уверен, какое значение использовать для a, чтобы метод не уничтожал фактический массив. - person Ajai; 05.11.2011

arrow_upward
0
arrow_downward

Кажется, я вижу, что произошло. вы, вероятно, изменили цикл, чтобы быть

for(int i=0; i<11; i++)
  ...

так как вы добавили дополнительный элемент в цикл. проблема в том, что это не XORing с 10, который не является числом в вашем массиве. Итак, алгоритм перестает работать.

int arr[11] = {0,1,2,3,4,5,6,7,8,4,9};
int a= 0;
for(int i=0;i<10;i++) {
  a= a^ arr[i] ^i;
}
a = a^arr[10];

cout<<a;

теперь его XOR выполняет числа от 0 до 9 дважды (что равно нулю) и 4 в дополнительный раз, поэтому результат должен быть 4.

person aleph_null    schedule 05.11.2011
comment
Опять же, как я уже упоминал выше, это отлично работает для отсортированного массива. - person Ajai; 05.11.2011