LeetCode 题解:1051. 高度检查器,JavaScript,桶排序,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 07 月 18 日

原题链接:https://leetcode-cn.com/problems/height-checker/



解题思路:



参考了O(n)解法,用时与内存击败100% java用户简单的桶排序



```javascript []

/**

 * @param {number[]} heights

 * @return {number}

 */

var heightChecker = function (heights) {

  // 创建一个桶,index对应0-100的数值,其值代表它出现的次数

  let bucket = new Array(101).fill(0);

  // 遍历heights,对heights中所有值进行计数

  // 例如heights为[1, 1, 4, 2, 1, 3],即可计算出其中有3个1,1个2,1个3,1个4

  for (let i = 0; i < heights.length; i++) {

    bucket[heights[i]]++;

  }

  // 统计最终未正常排序的结果

  let count = 0;

  // 按顺序遍历桶,相当于按顺序遍历了排序好的heights

  for (let i = 1, j = 0; i < bucket.length; i++) {

    // 每遍历到一个bucket[i]大于0,即为i还有数量,就将其值进行循环,

    while (bucket[i] > 0) {

      // 如果此时heights[j]的值与i的值不同,则表示该值未正确排序,即count++

      if (heights[j] !== i) {

        count++;

      }

      // 每次循环bucket[i]减1,表示i的数量减少1个

      bucket[i]--;

      // 每次i减1,都将heights数组的index加1,即j++

      j++;

    }

  }

  return count;

};

```



发布于: 2020 年 07 月 18 日 阅读数: 11
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:1051. 高度检查器,JavaScript,桶排序,详细注释