侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【位运算】数组中只出现一次的两个数字

GabrielxD
2022-10-04 / 0 评论 / 0 点赞 / 171 阅读 / 580 字
温馨提示:
本文最后更新于 2022-10-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

73. 数组中只出现一次的两个数字


一个整型数组里除了两个数字之外,其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

数据范围

数组长度 [1,1000][1,1000]

样例

输入:[1,2,3,3,4,4]

输出:[1,2]

解题

方法一:位运算

思路

设这两个落单的数分别是 a,ba, b,首先类似 【位运算】只出现一次的数字 把数组中所有数字异或起来可以得到两个落单数异或的结果,也就是:nums[1]nums[2]...nums[n1]=allXor=abnums[1] \oplus nums[2] \oplus ... \oplus nums[n-1] = allXor = a \oplus b,此时只需要求出其中一个落单的数就可以得到另一个数。

我们都知道异或运算得到的数的非零位就是这两个数不同的位,那么取到其中一个数与另一个数的不同位然后在 numsnums 中找到与该数该位相同的所有数再异或起来得到的就是其中的一个落单的数,来看一个例子:

nums=[5,5,6,7,9,9,7,3,3,2]
把所有的数异或起来得到 allXor=4(100(2))allXor=4(100_{(2)}),然后取出其最低的非零位:mask=100(2)mask = 100_{(2)},然后把数组中所有第 22 位是 11 的数异或起来:a=5(101(2))5(101(2))6(110(2))7(111(2))7(111(2))=6(110(2))a = 5(101_{(2)}) \oplus 5(101_{(2)}) \oplus 6(110_{(2)}) \oplus 7(111_{(2)}) \oplus 7(111_{(2)}) = 6(110_{(2)}) 这里拿到的 66 就是一个落单的数,然后把该数与 allXorallXor 进行异或运算就得到了另一个落单的数。

代码

class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        int allXor = 0;
        for (int num : nums) allXor ^= num;
        int mask = allXor & -allXor;
        int a = 0;
        for (int num : nums) {
            if ((num & mask) != 0) a ^= num;
        }
        return new int[]{a, allXor ^ a};
    }
}
0

评论区