js题解LeetCode1051 高度检查器哈希表对比

时间:2022-12-29 羊肉串人气:0

解题思路

方法一，实际上我们并不需要给heights进行排序，我们需要的只是从前往后遍历heights，找到在当前位置上是不是应该出现的最小的数字，因此

我们创建一个数组，存储所有出现的数字的次数，由于题目已经限制 heights 长度最大为 100，直接创建 100 长度的数组通过下标保存计数器即可，如果不定长度或者长度较大就得通过 map 处理然后对 map 排序了

遍历heights，在数组中存储所有数字出现的次数，同时找到最小值作为数组判断的起点
再遍历一遍 heights，判断当前遍历项是否跟目标下标一致，如果不一致结果+1，一致就不用管了，然后把计数器-1，直到 0

如果当前下标的值为 0 了，就证明heights中出现的该下边的数字次数已经用光了，直接迭代找到下一个不为 0 的下标继续即可

方法二，比较简单，直接对heights排序，然后逐位对比即可

代码

/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function (heights) {
  const arr = new Array(100).fill(0)
  let t = 0
  let idx = 101
  heights.forEach(item => {
    arr[item]++
    if (item < idx) idx = item
  })
  heights.forEach(item => {
    if (item !== idx) {
      t++
    }
    arr[idx]--
    while (arr[idx] === 0) {
      idx++
    }
  })
  return t
};
var heightChecker = function (heights) {
  const h = JSON.parse(JSON.stringify(heights))
  const arr = heights.sort((a, b) => a - b)
  let t = 0
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== h[i]) t++
  }
  return t
};

加载全部内容