剑指offer Binary Tree

剑指offer-数组中数字出现的次数 II

Posted by franki on May 19, 2021

数组中数字出现的次数 II

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

示例

输入：nums = [3,4,3,3]
输出：4

思路

利用hash的空间，记录数组中的每一个值出现的次数，接着遍历hash，找到出现一次的数字

代码

var singleNumber = function(nums) {
    if (nums.length == 0) {return null;}
    let hash = {};
    for (let i=0; i<nums.length; i++) {
        if (hash[nums[i]]) {
            hash[nums[i]]++;
        } else {
            hash[nums[i]] = 1;
        }
    }

    for (let key in hash) {
        if (hash[key] === 1) {
            return key;
        }
    }

    return null;
};

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(N)