算法-数组的重复数据

算法-数组的重复数据

Posted by limantang on March 26, 2019

寻找数组的中心索引

给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:

输入: [4,3,2,7,8,2,3,1]

输出: [2,3]

/**
 * @param {number[]} nums
 * @return {number}
 */
const findDuplicates = function(nums) {
    const hashMap = new Map();
    const length = nums.length;
    const result = [];
    let count;
    for (let i = 0; i < length; i++) {
        count = hashMap.get(nums[i]);
        if (!count) {
            hashMap.set(nums[i], 1)
        } else {
            hashMap.set(nums[i], ++count)
        }

        if (hashMap.get(nums[i]) === 2) {
            result.push(nums[i])
        }
    }
    return result;
};

思路

利用hashmap的特性来统计数组每个元素作为hashmap的key出现次数来统计 但是这种方法虽然在时间复杂度为O(n),但是开辟了额外的空间