欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指offer】面试题56(1):数组中只出现一次的两个数字

程序员文章站 2022-07-15 12:16:29
...

题目

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

有空再补上 0.0

代码

/**
 * 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 
 * @author peige
 */
public class _56_01_NumbersAppearOnce {

    /**
     * num1,num2分别为长度为1的数组。传出参数将num1[0],num2[0]设置为返回结果
     */
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || array.length < 2)
            return;
        int n = 0;
        for(int i = 0; i < array.length; ++i)
            n ^= array[i];
        int firstBitIs1 = findFirstBitIs1(n);
        int N = 1 << firstBitIs1;
        num1[0] = 0;
        num2[0] = 0;
        for(int i = 0; i < array.length; ++i) {
            if((array[i] & N) != 0)
                num1[0] ^= array[i];
            else
                num2[0] ^= array[i];
        }
    }

    private int findFirstBitIs1(int n) {
        if(n == 0)
            return 0;
        for(int i = 0; i < 32; ++i, n >>= 1) {
            if((n & 1) == 1)
                return i;
        }
        return 0;
    }
}

测试

public class _56_01_Test {

    public static void main(String[] args) {
        test1();
        test2();
    }

    private static void test1() {
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        _56_01_NumbersAppearOnce nao = new _56_01_NumbersAppearOnce();
        nao.FindNumsAppearOnce(new int[] {55,2,3,1,1,2,55,6,7,6}, num1, num2);
        System.out.println((num1[0] == 3 && num2[0] == 7) || (num1[0] == 7 && num2[0] == 3)); 
    }

    private static void test2() {
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        _56_01_NumbersAppearOnce nao = new _56_01_NumbersAppearOnce();
        nao.FindNumsAppearOnce(new int[] {55,2}, num1, num2);
        System.out.println((num1[0] == 55 && num2[0] == 2) || (num1[0] == 2 && num2[0] == 55)); 
    }
}