JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

Code

两轮循环

1. 第一轮得到3^5的值
0011
0110
——
0101

2. 通过 temp & -temp 得到最右边一位的1，并且把其他的位置全部赋值为0，得到0001
这样做是为了得到一个标志位。因为3&0001得到1，5&0001得到0，这是必然的。
并且由于其他的数字都是出现两次，所以他们^肯定都是0

3. 将数字分成两组
和0001&=0的放在一起，然后做^，最后肯定得到了5
和0001&=1的放到一起，然后做^，最后肯定得到了3

class Solution {
    public int[] singleNumber(int[] nums) {
        int temp = 0;
        for(int num : nums) {
            temp ^= num;
        }

        int bit = temp & (-temp);

        int[] res = new int[]{0, 0};

        for(int num : nums) {
            if((num & bit) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }

        return res;
    }
}

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        temp = 0

        for num in nums:
            temp ^= num

        res = [0, 0]
        bit = temp & -temp

        for num in nums:
            if bit & num == 0:
                res[0] ^= num
            else:
                res[1] ^= num

        return res