牛客网刷题-数组中只出现一次的两个数字

问题描述

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

示例

示例1

输入
[1,4,1,6]

输出
[4,6]

解决思路

思路

1. 这里主要是运用了异或^和与& 这两个运算的性质
   （1）异或^：相同为0，不同为1，两个相同的数字异或为0
   （2）与&：除了1&1，0&0，0&1，1&0均为0
2. 思路：
   （1）将数组所有的数字进行异或运算，得到了两个只出现一次的数字的异或结果
   （2）根据异或结果和与运算，找到第m位异或不同的位，也就是说从右向左找到第一个为1的位
   （3）根据与运算将数组拆分成两组，分别进行异或，得出两个数字。

数组：[1,4,1,6]
（1）异或结果：2
（2）第一个异或位：2的第二位为1 (2的二进制：1 0)
（3）将数组拆分：
第二位为1：[6] （6的二进制：1 1 0）
其他：[1,4,1] （1的二进制 0 1；4的二进制 1 0 0）
（4）分组后的结果：
6,4

代码实现

// 思路1
public class Solution {  
    public int[] FindNumsAppearOnce(int[] array) {
        // write code here
        int[] a = new int[2];
        int x = array[0];
        //将数组中的所有数字做异或处理
        //相同的数字异或结果为0， 0与数字x异或的结果为x
        //所以最终的结果为单独出现的数字的异或结果
        for (int i = 1; i < array.length; i++) {
            x ^= array[i];
        }
        //两个单独出现的数字若在m位相异，则在x中第m位为1
        //找到这样的m位
        // 因为两给数字异或有数值，说明两个数字存在异或的位数，找到从右边起，第一个异或的位数，也就是找到第一个1
        int m = 1;
        while ((m & x) == 0) {
            m = m << 1;
            System.out.println(m);
        }
        //根据第m位的值将原数组分为两组，单独出现的两个数字分在不同的组
        for (int i : array) {
            if ((m & i) == 0) {
                a[0] ^= i;
            } else {
                a[1] ^= i;
            }
        }
        if (a[0] > a[1]) {
            int temp = a[0];
            a[0] = a[1];
            a[1] = temp;
        }
        return a;
    }
}

时间复杂度分析：
O(N)：遍历数组

空间复杂度分析：
O(1)：除了运算结果，没有使用额外的空间

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

数组中只出现一次的两个数字-牛客网