美文网首页
颜色分类--75

颜色分类--75

作者: Joah_l | 来源:发表于2019-11-21 11:06 被阅读0次
    // 75 号; 颜色分类
    function sortColors(nums) {
      let obj = { 0: 0, 1: 0, 2: 0 }
    
      for (let i = 0, len = nums.length; i < len; i++) {
        let item = nums[i]
        if (!(item >= 0 && item <= 2)) {
          throw Error('error')
        }
        obj[item]++
      }
      // 下面三遍循环填充数据
    }
    
    // 三路快排的思想
    
    function sortColors2(nums) {
      let zeroIndex = -1; // nums[0...zero] ==> 0
      let twoIndex = nums.length // [two, n-1] ==> 2
      for (let i = 0; i < twoIndex;) {
        let item = nums[i]
        if (item === 1) {
          i++
        } else if (item === 2) {
          twoIndex--
          swap(nums[i], nums[twoIndex])
        } else {
          zeroIndex++
          swap(nums[zeroIndex], nums[i])
          // 在 i 的前面只可能是 0, 或者是 1
          i++
        }
      }
    }
    
    // 88(合并两个有序的数组(归并的过程)),
    // 215(在一个整数序列中寻找第 k 大的元素); 利用快排;
    

    相关文章

      网友评论

          本文标题:颜色分类--75

          本文链接:https://www.haomeiwen.com/subject/lsizictx.html