返回

[Leetcode]260. Single Number III(C++)

题目描述

题目链接:260. Single Number III

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.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

例子

例子 1

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

例子 2

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

例子 3

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

Follow Up

Note

Constraints

  • 2 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • Each integer in nums will appear twice, only two integers will appear once.

解题思路

这道题是[Leetcode]136. Single Number(C++) 的进阶版本,通过上一道题的经验可以知道,假设在这个数字中只出现过一次的数字分别是 a 和 b,那么我们将数组中所有数字异或最后的结果是 a 和 b 的异或,这个结果每一位为 1 都表示 a 和 b 在这一位上不同,假如我们只保留其中一位为 1,其他位全部置 0,设为bitflag。那我们可以保证 a 和 b 与它求与时,其中一个为 0,另一个不为 0,这样就可以得到一个区分条件:将数字中所有与bitflag相与为0的结果进行异或存入一个数中,另外的数字也进行异或存入另一个数字中,由于相同数字异或为0,因此最后得到的两个数字就是 a 和 b。

上述方法中,我们需要把第一次异或的结果置1位为1,其余置0。这个方法很多,可以一位一位遍历找是1的位,这里我们用这个小技巧 mask & ~(mask - 1) 求得结果,结果为1的位是异或结果中从右往左第一个为1的位。

代码如下:

#include <vector>
class Solution {
public:
    std::vector<int> singleNumber(std::vector<int>& nums) {
        // xormask = a ^  b
        long xormask = 0;
        for (int num : nums) {
            xormask ^= num;
        }

        // in bit mask, the right most different bit beween a and b is set to 1,
        // others are set to 0
        int bitmask = xormask & (~(xormask - 1));

        std::vector<int> ans(2, 0);
        for (int num : nums) {
            if ((num & bitmask) == 0) {
                ans[0] ^= num;
            } else {
                ans[1] ^= num;
            }
        }

        return ans;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 260.SingleNumberIii.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy