Leetcode JAVA刷刷站（75）颜色分类

2024/11/30 12:38:58 来源：https://blog.csdn.net/m0_73399576/article/details/141405632 浏览: 次关键词：Leetcode JAVA刷刷站（75）颜色分类

一、题目概述

二、思路方向

在Java中，要实现这个排序算法，我们可以使用三指针的方法，也称作荷兰国旗问题（Dutch National Flag Problem）。这个方法使用三个指针来分别追踪数组中小于、等于和大于中间值的元素的边界。在这个特定的问题中，中间值是1（代表白色），但我们实际上更关心的是将0（红色）放在前面，将2（蓝色）放在后面，而1（白色）则位于中间。

三、代码实现

public class Solution {  public void sortColors(int[] nums) {  if (nums == null || nums.length <= 1) {  return;  }  int low = 0; // 小于中间值的指针  int mid = 0; // 当前遍历的指针  int high = nums.length - 1; // 大于中间值的指针  while (mid <= high) {  if (nums[mid] == 0) {  // 如果当前元素是0，则与low指向的元素交换，并将两个指针都向前移动  swap(nums, low, mid);  low++;  mid++;  } else if (nums[mid] == 1) {  // 如果当前元素是1，则只将mid指针向前移动  mid++;  } else { // nums[mid] == 2  // 如果当前元素是2，则与high指向的元素交换，但只将high指针向后移动  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;  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] nums = {2, 0, 2, 1, 1, 0};  solution.sortColors(nums);  for (int num : nums) {  System.out.print(num + " ");  }  }  
}

执行结果：

四、小结

在这个代码中，low 指针用于追踪所有小于1（即0）的元素的边界，mid 指针用于遍历数组，high 指针用于追踪所有大于1（即2）的元素的边界。当mid指针遇到0时，它与low指针交换，并将两个指针都向前移动；当mid指针遇到1时，它只向前移动；当mid指针遇到2时，它与high指针交换，但只将high指针向后移动。这个过程一直持续到mid指针超过high指针为止，此时数组就被排序好了。