【LeetCode 136 137 260】只出现一次的数字Ⅰ、Ⅱ、Ⅲ （Single Number）

曾经终败给现在 2021-09-22 14:36 286阅读 0赞

LeetCode 第136、137、260刚好都是同一类型的题目：只出现一次的数字，放在一起进行整理

### 文章目录 ###

*   *  136. 只出现一次的数字Ⅰ
     *  137. 只出现一次的数字Ⅱ
     *  260. 只出现一次的数字Ⅲ

## 136. 只出现一次的数字Ⅰ ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
说明：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

*  示例 1:  
    输入: \[2,2,1\]  
    输出: 1
 *  示例 2:  
    输入: \[4,1,2,1,2\]  
    输出: 4

思路：这道题比较简单，相同的数可以用异或的方式处理掉，比如 a ^ a = 0，所以我们可以对数组内的所有数进行异或操作，每对相同的数被抵消，只剩下唯一那个只出现一次的元素

public int singleNumber(int[] nums) { 
            // 对输入进行判断
            if (nums == null) { 
                return 0;
            }
            int output = 0;
            // 遍历整个数组，进行异或处理
            for (int a : nums
                    ) { 
                output ^= a;
            }
            return output;
        }

## 137. 只出现一次的数字Ⅱ ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。  
说明：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

*  示例 1:  
    输入: \[2,2,3,2\]  
    输出: 3
 *  示例 2:  
    输入: \[0,1,0,1,0,1,99\]  
    输出: 99

思路：这里提供三种思路  
① 利用HashSet，遍历整个数组，将整个数组存入HashSet中，相当于重复的部分被删除了，计算有setSum（一套重复数字+只出现了一次的数），再计算整个数组所有元素的和totalSum（三套重复数字+只出现了一次的数），通过（setSum\*3-totalSum）/2。这种思路的代码：

private static int singleNubmer1(int[] A) { 
            if (A == null) { 
                return 0;
            }
            Set<Integer> set = new HashSet<>(A.length);
            int totalSum = 0, setSum = 0;
            for (int a : A
                 ) { 
                totalSum += a;
                if (!set.contains(a)) { 
                    set.add(a);
                    setSum += a;
                }
            }
            return (setSum * 3 - totalSum) / 2;
        }

但这种方法不适合于JAVA，因为在求和的过程中，可能因为数字太大，超过了Integer.MAX\_VALUE，而出现异常。这种思路可以用于python语言进行实现。而在一开始，指定了hashset的初始容量后，可以将整个算法的复杂度约为O(n)，但空间复杂度较大

② 将所有数的同一位进行相加，再对3进行取余，重复的数字会因为对3取余而被抵消掉，剩下的数即为不重复的数

private static int singleNumber(int[] A) { 
            int result = 0;
            // 遍历Integer的每一位
            for (int i = 0; i < 32; i++){ 
                int temp = 0;
                // 遍历每个数的同一位
                for (int a : A) { 
                    temp += (a>>i & 1);
                }
                // 对3取余
                result |= ((temp % 3) << i);
            }
            return result;
        }

这种做法时间复杂度为O(n)，下面是在leetcode官网提交的结果，还算是比较好的一种解法  
![在这里插入图片描述][70]

③ 后面突然搜到了别人的另外一种做法：  
https://blog.csdn.net/i\_am\_bird/article/details/78160627

private static int singleNumber2(int[] A) { 
            //记录只出现过1次的bits
            int ones = 0;
            //记录只出现过2次的bits
            int twos = 0;
            // 记录出现过3次的bits
            int threes;
            // 遍历所有数
            for (int i : A
                 ) { 
                // 通过现在的数跟出现一次的数进行并运算，找出出现了两次的数
                twos |= ones & i;
                // 除去出现了一次的数中当前的数
                ones ^= i;
                // 如果在出现两次中出现了，还在出现一次中出现，则说明出现了三次
                threes = ones & twos;
                // 将出现三次的情况在记录只出现过1次的bits中除去
                ones &= ~threes;
                // 将出现三次的情况在记录只出现过2次的bits中除去
                twos &= ~threes;
            }
            // 返回只出现一次的bits，即没有重复的数
            return ones;
        }

在leetcode官网提交的结果：  
![在这里插入图片描述][70 1]

## 260. 只出现一次的数字Ⅲ ##

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

*  示例 :  
    输入: \[1,2,1,3,2,5\]  
    输出: \[3,5\]  
    注意：  
    结果输出的顺序并不重要，对于上面的例子， \[5, 3\] 也是正确答案。  
    你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路：  
参考只出现一次的数字Ⅰ，对所有数进行异或操作，可以获得两个没有重复的数a、b的异或操作的结果。  
因为a、b是不同的数，则他们异或的结果一定至少存在一个1，找出其中的一个1，记为c。  
重新遍历数组，如果每个数跟c取与操作，如果相同，则归入集合A，如果不同则归入集合B，我们可知，集合A里面有一个不重复的数，和成对的其他重复的数，集合B里有另外一个重复的数，和成对的其他重复的数。相当于问题转为两个求只出现一次的数字Ⅰ的问题

这里举一个具体的例子解释一下：\{1，1，2，2，3，5，8，5，8，10\}  
其中不同的元素为：3（0011），10（1010）  
对整个数组进行异或操作，最后只剩下3跟10进行异或操作：1001  
我们可以通过获取其中的一个1，例如 c = 0001  
我们重新遍历整个数组，每个数与c进行与操作，判断是否为0，可以将数组分成：  
与为0：\{2，2，8，8，10\} 与为1：\{1，1，3，5，5\}  
刚好将两个不同的数字分开，且将重复的数字分到了相同的集合中，再对每个集合进行异或操作，即可以获得不同的数字

public int[] singleNumber(int[] nums) { 
            int a = 0;
            // 对整个数组进行异或操作
            for (int i : nums
                 ) { 
                a ^= i;
            }
            // 取一位1
            a &= -a;
            int[] result = new int[2];
            // 重新遍历数组，将数组进行分组
            for (int i : nums
                 ) { 
                if ((i & a) == 0) { 
                    result[0] ^= i;
                } else { 0
                    result[1] ^= i;
                }
            }
            return result;
        }

Leetcode官网运行结果：  
![在这里插入图片描述][70 2]  
[其他 LeetCode 题目解析][LeetCode]

[70]: /images/20210920/26a725b91fdb4667aa81d0a55780a370.png
[70 1]: /images/20210920/503faff18e7b43b0933d50e59d6bec43.png
[70 2]: /images/20210920/aaceec980ef14102bab9a747ed213813.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html