[路飞]_leetcode-75-颜色分类

[题目地址][B站地址]

给定一个包含红色、白色和蓝色，一共 n个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入： nums = [2,0,2,1,1,0]
输出： [0,0,1,1,2,2]
复制代码

示例 2：

输入： nums = [2,0,1]
输出： [0,1,2]
复制代码

示例 3：

输入： nums = [0]
输出： [0]
复制代码

示例 4：

输入： nums = [1]
输出： [1]
复制代码

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

本题要求我们原地对数组进行排序，所有原地排序其实就是在数组内移动元素的位置。

这里我们采用将所有的 0 移动到数组开头，所有的 2 移动到数组末尾的方式。

1. 获取数组长度 len,初始化 count = 0 记录循环次数，i = 0 记录当前处理元素下标。
2. 遍历数组，如果当前元素是 0,且不在数组开头，将其移动到数组开头，如果当前元素是 2，将其移动到数组末尾，并且 i--,因为此时后面的元素都向前移动了一位，为了能处理到所有元素，所以需要 i--,如果当前元素是 1，不进行处理。
3. 当遍历次数 count = len,就处理过了所有元素。

动画演示

代码实现

var sortColors = function(nums) {
  // 获取数组长度
  const len = nums.length;
  // 初始化遍历次数 当前元素下标
  let count = 0,i = 0;
  // 遍历输入数组
  while(count<len){
    const num = nums[i]
    // 单过当前元素为 0
    if(num === 0){
      // 将其移动到数组开头
      if(i!==0) nums.unshift(nums.splice(i,1))
    }
    // 如果当前元素为 2，将其移动到数组末尾，因为后面元素统一向前移动了一位，所以 i--
    else if(num === 2) nums.push(nums.splice(i,1)),i--
    // 更新遍历次数和当前元素下标
    count++,i++;
  }
};
复制代码

至此我们就完成了 leetcode-75-颜色分类

如有任何问题或建议，欢迎留言讨论！