Java描述 LeetCode，剑指 Offer 56 - I. 数组中数字出现的次数

????’???? ????????????, ???? ???????? ???? ???????????????????????????????? ???????????????????????????? ???????????????? ????????????????????????????, ????????????????????.

• ???? ????????????????????????: ???????????????????? ????????????????????????????????????????
• ???? ????????????????????????????????: ????’???? ???????????????????????????????????? ???????????????????????????????? ???????????????????????? ????????????????????????????, ????????????????????????????????, ???????????????????????????????????????????? ????????????????????????, ???????????????????????????????????????? ???????????? ???????? ????????.
• ???? ???????????? ???????? ???????????????????? ????????：????????
• ???? ???????? ????????????????: ????????????????????://????????????????????????????.????????????????.????????????????.????????????/
• ???? ???????????????????????????????????????????????? ????????????????????????：???????? ????????????????????
  

1-1：题目描述

一个整型数组 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.length <= 10000

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

1-2：位移运算解法

☘️首先分析题目，数组中有两个数字和其他数字不一样，其他数字都是成对的存在，只有他们俩是单个的。首先先复习下几个位移运算：

☘️对于成对出现的数字来说，他们经过异或就是0，比如111 ^ 111 = 0；可以先通过这点将数组中所有的数字进行^操作得到a^b的值，那么第一个问题，异或得有个初始值吧，什么样的值x与其他值y异或操作还是y呢？那必然是0，0和其他数异或还是0，（当然你可以把num[0]作为初值一样的），所以有下面的代码：

int a_b = 0;
for (int j : nums) {
    a_b ^= j;
}

☘️接着再想办法把a_b的值分开来，首先可以肯定a和b必然是不等的，不然就是出现两次了，我们利用不相等的数字的二进制中必然至少有一位是不相同的这一个关键点去解决，只要找到第一个不相同的位就可以成功把他们区分开来了，不相同的位在a_b（a_b代表a^b的值）中表现为1，相同的位表现为0。所以我们用1，不停的从右向左移动，做&运算，直到找到那个第一次出现1为止。代码如下：

int m = 1;
while ((m & a_b) == 0) {
    m = m << 1;
}

☘️那么m上记录的就是a和b第一个不同的位，对于全部的nums数组中其余成对存在的数而言，这个位上要么是0要么是1，所以我们按照这个位上数字的不同就可以分成两组，[a, x1, x2 ,x3 , x4…]；[b, y1, y2 , y3 , y4…] 前一个数组在这个位上是1，后一个是0，可以知道，xi和yj都是成对存在的。这样对这两个数组分别进行异或就可以把a和b单独搞出来了。全部代码如下：

public class Solution {
    public int[] singleNumbers(int[] nums) {
        // 异或，初始化为0不会影响到结果
        int a_b = 0;
        int m = 1;
        int x = 0, y = 0;
        for (int j : nums) {
            a_b ^= j;
        }
        while ((m & a_b) == 0) {
            m = m << 1;
        }
        for (int num : nums) {
            if ((m & num) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

最后

以上就是纯情电话最近收集整理的关于Java描述 LeetCode，剑指 Offer 56 - I. 数组中数字出现的次数的全部内容，更多相关Java描述内容请搜索靠谱客的其他文章。