LeetCode 0260 - Single Number III

Reck Zhang

发布于 2021-08-11 12:07:08

2260

发布于 2021-08-11 12:07:08

文章被收录于专栏：Reck Zhang

Single Number III

Desicription

Given an array of numbers 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.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int ret = 0;
        for(const auto& num : nums) {
            ret ^= num;
        }
        ret &= -ret;
        int ans_1 = 0;
        int ans_2 = 0;
        for(const auto& num : nums) {
            if((num & ret) > 0) {
                ans_1 ^= num;
            } else {
                ans_2 ^= num;
            }
        }
        return vector<int>{ans_1, ans_2};
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-12-11，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm