数组中数字出现的次数(重要题型)

2020-12-24

剑指 Offer 56 - I. 数组中数字出现的次数

难度中等

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

1 2	输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例 2：

1 2	输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

如果一个数组中除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

对全部数字异或操作即可得到结果，原因如下：

对于两个操作数的每一位，相同的时候结果位0，不同的时候结果为1.那么在计算的过程中，成对出现的数字的所有位会两两抵消为0，最终得到的结果就是那个在数组中只出现一次的数字。

如果可以把所有的数字分成两组，使得：

两个只出现一次的数字分在不同的组中；
出现两次的数字分在相同的组中；

那么这个问题就可以解决。

avatar

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

        int index = 1;
        while ((index & ret) == 0) {
            index = index << 1;
        }

        int number1 = 0, number2 = 0;

        for (int num : nums) {
            if ((num & index) == 0) number1 ^= num;
            else number2 ^= num;
        }

        return new int[]{number1, number2};
    }
}

参考文献

作者：LeetCode-Solution
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true