LeetCode_排序_中等_75.颜色分类

柔光的暖阳◎ 2023-10-06 18:43 36阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个包含红色、白色和蓝色，一共 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sort-colors

## 2.思路 ##

（1）原地排序  
分析题目可知，本体可以使用任意一种原地排序方法，即不申请多余的空间来进行的排序，常见的原地排序有**希尔排序**、**冒泡排序**、**插入排序**、**简单选择排序**、**堆排序**、**快速排序**等等，下面的代码中使用的是**简单交换排序**。

（2）移动元素 0 和 2  
分析题目可知，nums\[i\] 为 0、1 或 2，所以可以考虑在遍历数组时，**将值为 0 的元素移动到数组最左边，将值为 2 的元素移动到数组最右边，那么剩下中间的元素就为 1**，其具体步骤如下：

*  首先定义 index0 = 0 和 index2 = nums.length - 1这两个变量，其中 **index0** 表示指向数组左部分最后一个值为 0 的元素的下一个元素，**index2** 表示指向数组右部分第一个值为 2 的元素的上一个元素；
 *  开始遍历 nums 数组，如果 nums\[i\] = 0，则将其与 nums\[index0\] 交换，并且 index0++；如果 nums\[i\] = 2，则将其与 nums\[index2\] 交换，并且 `index2--`，由于时从前往后遍历数组，所以若此时交换后的 nums\[i\] 值可能为 0 或者 2，需要回退 i 重新处理该数；
 *  遍历结束后，原地排序就结束了。

## 3.代码实现（Java） ##

//思路1————原地排序（简单交换排序）
    class Solution {
        
        public void sortColors(int[] nums) {
        
            int length = nums.length;
            if (length <= 1) {
        
                return;
            }
            int temp;
            //简单交换排序
            for (int i = 0; i < length - 1; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
        }
    }

//思路2————移动元素 0 和 2
    class Solution {
        
        public void sortColors(int[] nums) {
        
            int length = nums.length;
            if (length <= 1) {
        
                return;
            }
            int index0 = 0;
            int index2 = length - 1;
            for (int i = 0; i <= index2; i++) {
        
                //如果 nums[i] = 0，则将其与 nums[index0] 交换
                if (nums[i] == 0) {
        
                    nums[i] = nums[index0];
                    nums[index0] = 0;
                    index0++;
                }
                //如果 nums[i] = 2，则将其与 nums[index2] 交换
                if (nums[i] == 2) {
        
                    nums[i] = nums[index2];
                    nums[index2] = 2;
                    index2--;
                    //若交换后 nums[i] != 1，则说明 nums[i] 有可能为 0 或者 2，需要回退 i 来处理这个数
                    if (nums[i] != 1) {
        
                        i--;
                    }
                }
            }
        }
    }