首页 > itarticle > 【剑指offer】数组中只出现一次的数字

【剑指offer】数组中只出现一次的数字

admin 11月 13, 2020 0

题目

一个整形数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

实现

public void (int[] array, int num1[], int num2[]) {
    if (array == null || array.length < 2)
        return;

    int result = 0;

    for (int i = 0; i < array.length; i++)
        result ^= array[i];

    int index = findFirstBitIsOne(result);

    for (int i = 0; i < array.length; i++) {
        if (isBitOne(array[i], index))
            num1[0] ^= array[i];
        else
            num2[0] ^= array[i];
    }
}

private int findFirstBitIsOne(int result) {
    int index = 0;

    while (index < 32 && (result & 1) == 0) {
        result >>= 1;
        index++;
    }

    return index;
}

private boolean isBitOne(int num, int index) {
    num >>= index;
    return (num & 1) == 1 ;
}