Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

260. Single Number III #268

Open
Tcdian opened this issue Jul 23, 2020 · 1 comment
Open

260. Single Number III #268

Tcdian opened this issue Jul 23, 2020 · 1 comment

Comments

@Tcdian
Copy link
Owner

Tcdian commented Jul 23, 2020

260. Single Number III

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

Example

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

Note

  • 结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
  • 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
@Tcdian
Copy link
Owner Author

Tcdian commented Jul 23, 2020

Solution

  • JavaScript Solution
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function(nums) {
    let bitmask = 0;
    for (let i = 0; i < nums.length; i++) {
        bitmask ^= nums[i];
    }
    const difference = bitmask & (-bitmask);
    let r1 = 0;
    let r2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (difference & nums[i]) {
            r1 ^= nums[i];
        } else {
            r2 ^= nums[i];
        }
    }
    return [r1, r2];
};
  • TypeScript Solution
function singleNumber(nums: number[]): number[] {
    let bitmask = 0;
    for (let i = 0; i < nums.length; i++) {
        bitmask ^= nums[i];
    }
    const difference = bitmask & (-bitmask);
    let r1 = 0;
    let r2 = 0;
    for (let i = 0; i < nums.length; i++) {
        if (difference & nums[i]) {
            r1 ^= nums[i];
        } else {
            r2 ^= nums[i];
        }
    }
    return [r1, r2];
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant