[Algorithm] 136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,1]

Output: 1
Example 2:
Input: [4,1,2,1,2]

Output: 4

var singleNumber = function(nums) {

    let res = ;

    for (let i = ; i < nums.length; i++) {

        res = res ^ nums[i]

    }

    return res;

};

It uses XOR: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#Bitwise_XOR

For example, 4 ^ 2

4: 0100

2: 0010

XOR

0110 => 6

But

2: 0010

XOR

0000 => 0

巴特西

[Algorithm] 136. Single Number

最新文章

热门文章