leetcode hot100【LeetCode 75.颜色分类】java实现

2025/7/3 21:48:13 来源：https://blog.csdn.net/qq_14815605/article/details/144055299 浏览: 次关键词：leetcode hot100【LeetCode 75.颜色分类】java实现

LeetCode 75.颜色分类

题目描述

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

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

示例 2:

输入: [2,0,1]
输出: [0,1,2]

Java实现解法

解法一：(单指针)

class Solution {public void sortColors(int[] nums) {int n = nums.length;int ptr = 0;for (int i = 0; i < n; i++) {if (nums[i] == 0) {int temp = nums[i];nums[i] = nums[ptr];nums[ptr] = temp;ptr++;}}for (int i = ptr; i < n; i++) {if (nums[i] == 1) {int temp = nums[i];nums[i] = nums[ptr];nums[ptr] = temp;ptr++;}}}
}

解法二：(三指针)

public class Solution {public void sortColors(int[] nums) {int low = 0, mid = 0, high = nums.length - 1;while (mid <= high) {if (nums[mid] == 0) {// 将 0 移到低端swap(nums, low, mid);low++;mid++;} else if (nums[mid] == 1) {// 1 已经在正确的位置，继续遍历mid++;} else {// 将 2 移到高端swap(nums, mid, high);high--;}}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

解题思路

单指针
我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。
在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。
此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。

三指针
这道题的要求是要原地排序数组，并且要尽量高效。我们可以利用荷兰国旗问题的算法来实现，它是一种基于三路快排的思想。
荷兰国旗问题的核心思想是通过三个指针将数组分为三个部分：
小于 1（红色）的部分。
等于 1（白色）的部分。
大于 1（蓝色）的部分。
使用三个指针：low，mid 和 high。
low 指针指向小于 1 的区域的最后一个元素，mid 指针遍历整个数组，high 指针指向大于 1 的区域的第一个元素。
遍历过程中：
如果 nums[mid] == 0，将其与 nums[low] 交换，并将 low 和 mid 指针向右移动。
如果 nums[mid] == 1，则 mid 向右移动。
如果 nums[mid] == 2，将其与 nums[high] 交换，并将 high 向左移动。