Высокоэффективный алгоритм получения номера из массива

Question

Вот проблема:

В одном массиве 2 * N + 1 целых чисел, и есть N парных чисел int, i, e, два 1 или два 3 и т. Д.одно целое число, у которого нет пары.

Вопрос в том, как найти это число с помощью высокоэффективного алгоритма.

Спасибо за любые подсказки или комментарии.

Answer 1

Хорошо, хорошо, вот объяснение моего комментария. : - /

missingNum = 0
for each value in list
   missingNum = missingNum ^ value //^ = xor
next
print(missingNum)

Это линейный алгоритм, O (n).

Так что здесь происходит? Скажем, у нас есть [2,1,3,1,2], для тех, кто знаком с оператором XOR, знаем, что 1 ^ 1 = 0, 0 ^ 0 = 0 и 1 ^ 0 = 1, 0 ^ 1 = 1 (помните, что нет переноса)

Таким образом, по существу, когда мы XOR последовательность битов (100110111), и она имеет четные числа 1, каждый из них будет XOR к нулю ... если число 1's нечетное, XOR дает 1

Итак, в нашем примере, начиная с lsb

2 : 0010
1 : 0001
3 : 0011
1 : 0001
2 : 0010

lsb bit: 0 ^ 1 ^ 1 ^ 1 ^ 0 : 1 
2nd bit: 1 ^ 0 ^ 1 ^ 0 ^ 1 : 1 
3rd bit: 0 ^ 0 ^ 0 ^ 0 ^ 0 : 0 
4th bit: 0 ^ 0 ^ 0 ^ 0 ^ 0 : 0

Итак, наше пропущенное число

0011 = 3

Answer 2

Более универсальный ответ вы можете найти в этом вопросе .Если вы предполагаете n=2, m=1, вы получите то, что хотите.

Но, как сказал st0le, в вашем случае XOR должно быть достаточно.

Answer 3

Если я правильно понял вопрос, у вас есть массив, содержащий нечетное число целочисленных значений, состоящее из числа целых чисел, которые появляются дважды, и одного целого числа, которое появляется только один раз.Например, массив может выглядеть так:

[3, 41, 6, 6, 41]

, где 6 и 41 повторяются, а 3 уникален.

Было бы хорошо узнать, есть ли другие ограничения.Например:

1. Массив отсортирован?(Если это так, эту простую проблему решить за O (N) время без необходимости временного хранения.)
2. Может ли непарное целое число совпадать с целым числом в паре?Например, является ли [1, 2, 2, 2, 1] допустимым входным значением, представляющим собой пару из 1, пару из 2 и непарную 2?

Предполагая, что массив не отсортирован, вот одно решение, выраженное в псевдокоде, котороевыполняется за время O (N) и снова требует не более половины пространства хранения исходного массива.

SEEN = []
for N in ARRAY:
    if N in SEEN:
        remove N from SEEN
    else:
        add N to SEEN

if size of SEEN != 1:
    error - ARRAY doesn't contain exactly 1 un-paired value
else:
    answer = SEEN[0]

Вот пример реализации, использующей NSMutableDictionary для хранения видимых значений, при условии, что исходный массив являетсяобычный массив C

#import <Foundation/Foundation.h>

int main(int argc, char argv[]) {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    int array[9] = {3, 4, 5, 6, 7, 6, 5, 4, 3};

    NSMutableDictionary *d = [NSMutableDictionary dictionaryWithCapacity:16];

    for (int i = 0; i < sizeof(array)/sizeof(int); i++) {
        NSNumber *num = [NSNumber numberWithInt:array[i]];
        if ([d objectForKey:num]) {
            [d removeObjectForKey:num];
        } else {
            [d setObject:[NSNull null] forKey:num];
        }
    }

    if ([d count] == 1) {
        NSLog(@"Unpaired number: %i", [[[d keyEnumerator] nextObject] intValue]);
    } else {
        NSLog(@"Error: Expected 1 unpaired number, found %u", [d count]);
    }


    [pool release];
    return 1;
}

И вот оно работает:

$ gcc -lobjc -framework Foundation -std=c99 demo.m ; ./a.out 
2010-12-25 11:23:21.426 a.out[17544:903] Unpaired number: 7