【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+" ");
        }
    }
}