I题目描述:

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

解析:

位运算和Hashmap

Java:

class Solution {
    public int[] singleNumbers(int[] nums) {
        int a = 0, b = 0;
        for(int i = 0 ; i < nums.length; i++) {
            a ^= nums[i];
        }
        int bit = a & -a;
        a = 0;
        for(int i = 0; i < nums.length; i++) {
            if((nums[i] & bit) == bit) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return new int[]{a, b};
    }
}

JavaScript:

var singleNumbers = function(nums) {
    let map = new Map();
    for(let i = 0; i < nums.length; i++) {
        if(!map.has(nums[i])) {
            map.set(nums[i]);
        } else {
            delete map.delete(nums[i]);
        }
    }
    return [...map.keys()];
};

II题目描述:

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

解析:

位运算和Hashmap

Java:

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        int[] count = new int[32];
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < 32; j++) {
                count[31 - j] += (nums[i] >> j) & 1;
            }
        }
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            if(count[i] % 3 != 0) {
                res |= 1;
            }
        }
        return res;
    }
}

JavaScript:

var singleNumber = function(nums) {
    let res = 0;
    let map = new Map();
    for(let i = 0; i < nums.length; i++) {
        if(!map.has(nums[i])) {
            map.set(nums[i], 1);
        } else {
            map.set(nums[i], map.get(nums[i]) + 1);
        }
    }
    for(let num of nums) {
        if(map.get(num) === 1) {
            res = num;
        }
    }
    return res;
};