时间戳

首页 > 解决方案 > 如果将 Map 的值保存为数组而不是遍历地图，是否可以节省时间复杂度？

javascript - 如果将 Map 的值保存为数组而不是遍历地图，是否可以节省时间复杂度？

问题描述

我在 JS 中使用地图来存储元素的出现次数，但我不确定是否应该将元素也存储为值以便更快地访问它。作为参考，我正在解决 LeetCode 上的 Single Number II ( https://leetcode.com/problems/single-number-ii/ )。

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

这是我的想法：将每个键也存储为一个值，以便我可以轻松过滤它们并获取键。另一种选择是遍历整个地图：

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hashmap = new HashMap<>();
    for (int num : nums)
      hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);

    for (int k : hashmap.keySet())
      if (hashmap.get(k) == 1) return k;
    return -1;
  }
}

以上解决方案来自 LeetCode 解决方案页面。

首选这些方法中的哪一种？关于时间复杂度，一个比另一个更好吗？

标签： javascripthashmap

解决方案

这是我想做的事情：将每个键也存储为值

不，你不应该那样做。它只是创建不必要的元组对象，不必要地占用内存。访问地图时很容易获得密钥。

这样我就可以轻松过滤它们并获取密钥。[没有]迭代[ing]整个地图

您已经在遍历整个地图，就是[...map.values()]这样。实际上，您不应该这样做，因为您不需要遍历整个映射并过滤与条件匹配的所有值，您只想找到第一个并在获得它后中断迭代。

当您同时需要键和值时，迭代 JavaScript 的正确方法Map是使用它的.entries()方法，这也是默认的迭代器：

function singleNumber(nums) {
    const  map = new Map();
    for (const num of nums) {
        const val = map.has(num) ? map.get(num) : 0;
        map.set(num, val + 1)
    }
    for (let [key, val] of map) {
        if (val === 1) {
            return key;
        }
    }
    return -1; // or null or undefined or something
}

推荐阅读