136.md

136. Single Number

Description

Given an 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?

Solution

Solution 1

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    "use strict";
    let table = {};
    for (let i = 0; i < nums.length; i++) {
        if (!table[nums[i]]) {
            table[nums[i]] = 1;
        } else {
            table[nums[i]]++;
        }
    }
    for (let key of Object.keys(table)) {
        if (table[key] === 1) {
            return parseInt(key);
        }
    }
};

Solution 2

/**
 * Solved with bit manipulation (XOR)
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    "use strict";
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        result ^= nums[i];
    }
    return result;
};