【搞定算法】找出数组中只出现一次的那个数，其他都出现两次【字节跳动面试题】

左手的ㄟ右手 2021-10-23 23:36 189阅读 0赞

> 博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：**pcwl\_Java** 一起交流秋招面试经验，可获得博主的秋招简历和复习笔记。

> **题目：找出数组中只出现一次的那个数，其他都出现两次。**
> 
> 要求：时间复杂度O(N)、空间复杂度O(1)

这道题因为要求了空间复杂度为 O(1)，因此无法使用 map 的形式记录出现的次数来解题。

*  **分析：**

**任何一个数字异或自己都等于 0。**

如果我们从头到尾依次异或数组中的每一个数，那么最终的结果就是那个只出现一次的数字，因为其他出现两次的数字全部在异或中被抵消为 0 了。

> 异或运算遵循交换分配率，举个栗子：2  3  4  2  3
> 
> 所有数字依次异或运算：2 xor 3 xor 4 xor 2 xor 3 = (2 xor 2) xor (3 xor 3) xor 4= 0 xor 0 xor 4 = 4
> 
> 最终结果 4 就是我们要找的那个只出现一次的数字

*  **代码实现：**

public class FindOnlyAppearOnce {
    
        public static int findOnlyAppearOnce(int[] arr){
            if(arr == null || arr.length == 0){
                return Integer.MIN_VALUE;
            }
            int res = arr[0];
            for(int i = 1; i < arr.length; i++){
                res ^= arr[i];
            }
            return res;
        }
    
        public static void main(String[] args) {
            int[] arr = {1, 1, 2, 2, 3};
            System.out.println(findOnlyAppearOnce(arr));  // 3
        }
    }

*  ### 扩展 1： ###

数组 A 中，除了某一个数字 x 之外，其他数字都出现了三次，而 x 出现了一次。请给出最快的方法找到 x。应该如何思考呢？

如果是两个相同的就可以利用两个相同的数异或结果为 0 来计算的，但这个题目中其他数字是出现了 3 次，因此肯定不可以再使用异或了。我们换一个角度来看，如果数组中没有 x，那么数组中所有的数字都出现了 3 次，在二进制上，每位上 1 的个数肯定也能被 3 整除。如 \{1, 5, 1, 5, 1, 5\} 从二进制上看有：

> 1：0001
> 
> 5：0101
> 
> 1：0001
> 
> 5：0101
> 
> 1：0001
> 
> 5：0101

二进制第 0 位上有 6 个 1，第 2 位上有 3 个 1。第 1 位和第 3 位上都是 0 个 1，每一位上的统计结果都可以被 3 整除。而再对该数组添加任何一个数，如果这个数在二进制的某位上为 1 都将导致该位上 1 的个数不能被3整除。因此通过统计二进制上每位 1 的个数就可以推断出 x 在该位置上是 0 还是 1 了，这样就能计算出 x 了。

推广一下，所有其他数字出现 N（N >= 2）次，而一个数字出现1次都可以用这种解法来推导出这个出现 1 次的数字。

public class FindOnlyAppearOnce {
    
        public static int findOnlyOccurOnce(int[] arr){
            if(arr == null || arr.length == 0){
                return Integer.MIN_VALUE;
            }
            int[] bits = new int[32];
            // 所有位置上的元素都初始化为0
            Arrays.fill(bits,0);
            for(int i = 0; i < arr.length; i++){
                for(int j = 0; j < 32; j++){
                    // 统计每个位置上1的个数
                    bits[j] += ((arr[i] >> j) & 1);
                }
            }
            // 如果某个位置上1的总数不能被3整除，那么目标数一定在这个位置上
            int res = 0;
            for(int i = 0; i < 32; i++){
                if(bits[i] % 3 != 0){
                    res += (1 << i);
                }
            }
            return res;
        }
    }

*  ### 扩展：2 ###

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(N)，空间复杂度是 O(1)  --> [https://blog.csdn.net/sinat\_34166518/article/details/88877308][https_blog.csdn.net_sinat_34166518_article_details_88877308]

[https_blog.csdn.net_sinat_34166518_article_details_88877308]: https://blog.csdn.net/sinat_34166518/article/details/88877308