【Hot100】LeetCode—75. 颜色分类

---

• 原题链接：75. 颜色分类

---

1- 思路

题目识别

• 识别1 ：给定三种类型数据，使得三种数据用一次遍历实现三种数据排序。

技巧

• 用两条线将数组分为三部分
• A 线左侧，保证数据都为 0 ；B 线右侧保证元素都是 2。

---

2- 实现

⭐75. 颜色分类——题解思路

class Solution {public void sortColors(int[] nums) {int left = 0;int right = nums.length-1;for(int i = 0 ; i <= right;i++){if(nums[i] == 0){swap(nums,i,left++);}else if(nums[i] == 2){swap(nums,i--,right--);}}}private void swap(int[] nums,int i,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

---

3- ACM 实现

public class sortColors {public static void sortC(int[] nums){int left = 0;int right = nums.length-1;for(int i = 0 ; i <= right;i++){if(nums[i] == 0){swap(nums,i,left++);}else if(nums[i] == 2){swap(nums,i--,right--);}}}private static void swap(int[] nums,int i ,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i= 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}sortC(nums);System.out.println("结果是");for(int i : nums){System.out.print(i+" ");}}
}