260. 只出现一次的数字 III --LeetCode每日一题打卡

题目链接

 260. 只出现一次的数字 III - 力扣(LeetCode)  

题目描述

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

示例 

示例 1:

                   输入:nums = [1,2,1,3,2,5]
                   输出:[3,5]
                   解释:[5, 3] 也是有效的答案。


示例 2:

                    输入:nums = [-1,0]
                    输出:[-1,0]


示例 3:

                   输入:nums = [0,1]
                   输出:[1,0]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-iii

提示 

2     <=     nums.length        <=  3 * 104
- 2 ^ 31     <=        nums[i]           <=  2 ^ 31 - 1
除两个只出现一次的整数外,nums 中的其他数字都出现两次。

思路 

我们知道两个不同的数,它们的二进制表示至少有一位不同。

此时我们可以通过异或操作来知道两个数中不同的数位,再通过lowbit(n)取出最右侧的 1,此处记作第k位。

   然后我们可以把数组中的数划分为两部分:

  • 第k位为1
  • 第k位不为1

而分别出现一次的数,一定在这两部分各占一个。

我们可以通过与运算 & 来判断第k位是否为1,然后把第k位为1的全部异或一遍,最后的得到的数一定是其中一个。 

260. 只出现一次的数字 III --LeetCode每日一题打卡

代码 

class Solution {
    public int[] singleNumber(int[] nums) {
        int cur1 = 0, cur2 = 0, cur = 0;
        for(int item : nums){
            cur1 ^= item;
        }
        cur = cur1 & ( - cur1);
        for(int item : nums){
            if((cur & item) == cur){
                cur2 ^= item;
            }
        }
        return new int[]{cur1 ^ cur2, cur2};
    }
}

补充 

朝着一个既定的方向去努力,就算再没有天赋,在时间的积累下也能稍稍有点成就吧。 

加油呀,快起床去刷题吧。          ————虽菜但在努力的小鲨鱼

260. 只出现一次的数字 III --LeetCode每日一题打卡

上一篇:LeetCode 21.合并两个有序链表


下一篇:两个单链表相交的一系列问题