75、颜色分类

;(function () {
  /**
   * 75. 颜色分类
   * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
   * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
   * 必须在不使用库的sort函数的情况下解决这个问题。
   *
   * 输入：nums = [2,0,2,1,1,0]
   * 输出：[0,0,1,1,2,2]
   *
   * 输入：nums = [2,0,1]
   * 输出：[0,1,2]
   *
   * 进阶：
   * 你可以不使用代码库中的排序函数来解决这道题吗？
   * 你能想出一个仅使用常数空间的一趟扫描算法吗？
   *
   */

  function sortColors(nums: number[]): void {
    // 方法一：冒泡排序
    // let len = nums.length;
    // let j = 0;
    // while (j < len) {
    //     for (let i = 0; i < len - j; i++) {
    //         if (i > 0 && nums[i] < nums[i - 1]) {
    //             let temp = nums[i];
    //             nums[i] = nums[i - 1]
    //             nums[i -1] = temp
    //         }
    //     }
    //     j++;
    // }

    // 方法二： 方法一变形
    // let right = 0;
    // let len = nums.length;
    // while(right < len) {
    //     for (let left = 0; left < len - right; left++) {
    //         if (left > 0 && nums[left] < nums[left - 1]) {
    //             [nums[left], nums[left - 1]] = [nums[left -1], nums[left]]
    //         }
    //     }
    //     right++
    // }

    // 方法三：单指针 遍历 --- 0 往数组前面丢，2 往数组后面丢
    // let len = nums.length;
    // let k = 0;
    // for (let i = 0; i < len; i++) {
    //     if (nums[i] === 0) {
    //         let temp = nums[i]
    //         nums[i] = nums[k]
    //         nums[k] = temp
    //         k++
    //     }
    // }
    // for (let j = k; j < len; j++) {
    //     if (nums[j] === 1) {
    //         let temp = nums[j]
    //         nums[j] = nums[k]
    //         nums[k] = temp
    //         k++
    //     }
    // }

    // 方法四： 双指针
    let len = nums.length
    let p0 = 0,
      p1 = 0
    for (let i = 0; i < len; i++) {
      if (nums[i] === 1) {
        let temp = nums[i]
        nums[i] = nums[p1]
        nums[p1] = temp
        ++p1
      } else if (nums[i] === 0) {
        let temp = nums[i]
        nums[i] = nums[p0]
        nums[p0] = temp
        if (p0 < p1) {
          temp = nums[i]
          nums[i] = nums[p1]
          nums[p1] = temp
        }
        ++p0
        ++p1
      }
    }
    console.log(nums)

    // 方法五： 双指针
    // let len = nums.length;
    // let p0 = 0, p2 = 0;

    // 方法六：标准桶排序 --- 统计出数组中 0, 1, 20,1,2 的个数，再根据它们的数量，重写整个数组
    // let n0 = 0, n1 = 0, n2 = 0;
    // for (let i = 0; i < nums.length; i++) {
    //     nums[i] === 0 && n0++;
    //     nums[i] === 1 && n1++;
    //     nums[i] === 2 && n2++;
    // }
    // for (let j = 0; j < nums.length; j++) {
    //     if (j < n0) {
    //         nums[j] = 0
    //     } else if (j < n0 + n1) {
    //         nums[j] = 1
    //     } else {
    //         nums[j] = 2
    //     }
    // }
  }

  let nums = [2, 0, 2, 1, 1, 0]
  sortColors(nums)
})()
75、颜色分类 ​

75、颜色分类
