当前位置:网站首页>【LeetCode】 101 颜色分类

【LeetCode】 101 颜色分类

2020-12-06 23:09:45 JaneRoad

题目:

image-20201206225809675

image-20201206225745124

解题思路:

对数组进行两次遍历。在第一次遍历中,我们将数组中所有的 00 交换到数组的头部。

在第二次遍历中,我们将数组中所有的 11 交换到头部的 00 之后。此时,所有的 22 都出现在数组的尾部,这样我们就完成了排序。

链接:https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

代码:

public class LC74 {

    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 static void main(String[] args) {
        LC74 lc74 = new LC74();
        int[] nums = new int[]{2,0,2,1,1,0};
        lc74.sortColors(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }

    }
}

版权声明
本文为[JaneRoad]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4248053/blog/4777178