力扣练习日记——只出现一次的数字

力扣练习日记——只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

异或方法

这里先上代码

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int k = 0;
        for (int num : nums) {
            k = k ^ num;
        }
        return k;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4, 1, 2, 1, 2};
//        int[] nums = new int[]{2, 2, 1};
        System.out.println(singleNumber(nums));
    }
}

这里运用的定义是：相同的数字，与自己异或的结果为0

因为数组中，只有一个数字出现了一次，其他数字都出现了两次，所以 k ^= num的结果为那个唯一出现一次的数字，以上。

扩展——只出现一次的两个数字

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
：
2 <= nums <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这里用的也是异或，先上代码

public static int[] singleNumbers(int[] nums) {
        int k = 0;
        for (int num : nums) {
            k ^= num;
        }

        int mask = 1;
        while((k & mask) == 0){
            mask <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if ((mask & num) == 0){
                a ^= num;
            }else{
                b ^= num;
            }
        }

        return new int[]{a, b};
    }

    public static void main(String[] args) {
//        int[] nums = {4,1,4,6};
        int[] nums = {1,2,10,4,1,4,3,3};
        System.out.println(Arrays.toString(singleNumbers(nums)));
    }

（这里参照的是力扣某大佬的思路，为了深化记忆，遂记录一下）

这里看出来，除了正常的异或之外，还多了一些操作，具体是什么呢？

我们来解析一下：

首先k ^= num之后呢，这里的结果相当于要返回的两个数字a和b的异或，即 k = a ^ b。

这个时候，我们需要把a和b两个数字分开，那么我们怎么分开呢？

这里，我们先找到a与b不同的最低位，即

int mask = 1;
while((k & mask) == 0){
    mask <<= 1;
}

此时，mask代表a与b不同的最低位，这个时候，用mask和num异或，为0的和a异或，为1的和b异或，这样能保证所求结果的两个数在不同的组中。异或完成则得到结果。