算法初级——数组中只出现一次的数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
知识点:异或操作,任何数与本身异或等于0 异或就是同为0,异为1.
位运算 << 左移一位,二进制10 (10<<1)——>(100) >>右移一位
判断两个只出现了一次的数字,先将所有元素异或操作,结果为两个只出现一次的的元素异或的结果,找出sum的第一位为1的数字,(两个不一样的数字一定有某些位置数字不一样,找出第一个不一样的数字),以这个位置将元素分为两部分,一部分该位置是一种,另一部分是另一种,完成两部分的分隔,此时每一部分包含一个单次元素,将两部分分别全部异或操作,结果就是所求元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class 数组中只出现一次的数字 {
    public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        //判断长度
        if(array == null || array.length <= 1){
            num1[0] = num2[0] = 0;
            return;
        }
        //定义变量
        int len = array.length, index = 0, sum = 0;
        //数组所有元素异或操作,结果为两个只出现一次的元素的异或
        for(int i = 0; i < len; i++){
            sum ^= array[i];
        }
        System.out.println("sum:"+sum);
        //<<位运算符 左移一位  二进制 10左移变成100,找到第一个1
        for(index = 0; index < 32; index++){
            if((sum & (1 << index)) != 0) break;
        }
        System.out.println("index:"+index);
        for(int i = 0; i < len; i++){
            if((array[i] & (1 << index))!=0){
                num2[0] ^= array[i];
            }else{
                System.out.println(array[i]);
                num1[0] ^= array[i];
            }
        }
        System.out.println(num1[0]+" "+num2[0]);
    }

    public static void main(String[] args) {
        int[] a = {3,3,4,4,5,5,6,6,7,8,8,44,99,99};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        FindNumsAppearOnce(a,num1,num2);
    }

}
0 条评论
发表一条评论