力扣：只出现一次的数字|，||，|||

谁借莪１个温暖的怀抱￠ 2023-10-04 15:25 17阅读 0赞

先上第一题目：

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

1.其实如果了解异或的性质的话很容易写出答案

class Solution {
        public int singleNumber(int[] nums) {
            int x=0;
            for(int i=0;i<nums.length;i++){
                    x=x^nums[i];
            }
            return x;
        }
    }

如果没想到异或或者不了解异或（^）的我也把它的性质写一下

> 1.  交换律：a ^ b ^ c <=> a ^ c ^ b
> 2.  任何数于0异或为任何数 0 ^ n => n
> 3.  相同的数异或为0: n ^ n => 0

我们这利用的就算它的2和3的性质，**相同的数全部异或以后就为0，而单独剩下的数异或0后不变，所以整个数组异或后剩下的就是我们的答案。**

**想到遍历的要认真反省一下了。。。。**

--------------------

再来看下进阶的题目：

给你一个整数数组 `nums` ，除某个元素仅出现 **一次** 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

很容易看出相比之前唯一的变化的数量加多了1，而这恰恰就是为了不能让你直接使用异或操作符，因为即使用了你重复的数字仍然还有1个，但我们依旧可以第一题为基础展开思考。

public static int singleNumber(int[] nums) {
            int x=nums.length/3;
            int count=0;
            Arrays.sort(nums);
            for(int i=0;i<nums.length-2;i++){
                if(nums[i]!=nums[i+1]||nums[i]!=nums[i+2])
                {
                    return nums[i] ^ nums[i + 1] ^ nums[i + 2];
                }
                count++;
                if(count==x)
                {
                    break;
                }
                i+=2;
            }
            return nums[nums.length-1];
        }

**思路：虽然重复数字的数量增加到三个，但我们可以先将数组排成升序，然后将三个三个进行捆绑比较，如果三个一样那么直接进行将i的值加三对下三个进行比较。如果到某组三个数不完全相等，那么也一定有两个数是相等的，这时我们只需要对这三个数进行异或即可得到答案。这种i一次性加3的情况下，很容易栈溢出。由题目可知数组的长度除以3肯定是余1的，所以我们把它对3取整得到它有多少组三个数，同时用计数器count计算已经检验过几组三个数，再检查完后及时跳出循序，此时还没得到答案说明前面每组三个数都相等，说明最后一个单独的数就是答案，只需将它返回即可。**

当然力扣上题解里还有大佬们各种厉害的方法，也应该多去学习一下。

3.再次进阶的题目

> 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 **任意顺序** 返回答案。

真没做出来哎心累。。。copy了一份答案

**思路：**

**首先利用相同值异或为0的特性，把整个数组进行异或操作，抵消后得到xOy  
接下来我们要利用xOy这个异或结果，拆分出x和y具体的数值  
假设xOy的值为0010，根据异或的特点，同一位相同为0，不相同为1，也就是说x和y在异或结果为1的这一位上（即第二个位置）不同  
根据第四点，我们先对xOy进行移位查找，找到结果为1的位div  
然后我们重新遍历数组，对每一个数进行分组，将div这一位数值分别为0和1的数字分为两组（相同数值每一位都相同，会分到同一组，而唯一的两个数字这一位不同，会被分到两组）  
当两组异或操作结束，相同的数字被抵消掉，两组剩下的结果值就是我们要找的两个唯一值**

class Solution {
        public int[] singleNumber(int[] nums) {
            int ret = 0;
            for (int n : nums) {
                ret ^= n;
            }
            int div = 1;
            while ((div & ret) == 0) {
                div <<= 1;
            }
            int a = 0, b = 0;
            for (int n : nums) {
                if ((div & n) != 0) {
                    a ^= n;
                } else {
                    b ^= n;
                }
            }
            return new int[]{a, b};
        }
    }

对二进制不熟根本理解不了分组只能流泪