leecode75. 颜色分类

75. 颜色分类

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

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]

输出：[0,1,2]

思路1:由题意可知此题需要将数组进行排序，因此第一个出现在脑子里面的就是快排。

代码如下：

class Solution {

    public void sortColors(int[] nums) {

        quickSort(nums,0,nums.length-1);

    }

    public void quickSort(int[] nums,int l,int r){

        int i =l;

        int j = r;

        if(l>r){

            return;

        }

        int temp = nums[l];

        int t =0;

        while(i!=j){

            while(nums[j]>=temp&&j>i){

                j--;

            }

            while(nums[i]<=temp&&i<j){

                i++;

            }

            if(i<j){

                t=nums[i];

                nums[i] =nums[j];

                nums[j]=t;

            }

        }

        nums[l] = nums[i];

        nums[i] = temp;

        quickSort(nums,l, i-1);

        quickSort(nums,i+1, r);

    }

}

思路2：由于本体出现的整数是固定的，因此可以分别记录0、1、2出现的次数，直接进行更改数组操作。即0出现了多少次数组前几个就是0，1、2同理

思路3：0，1，2 排序。一次遍历，如果是0，则移动到表头，如果是2，则移动到表尾，不用考虑1。0和2处理完，1即为正确。

代码如下：

class Solution {

    public void sortColors(int[] nums) {

        int N = nums.length;

        int smallEdge = 0;

        int bigEdge = N - 1;

        for (int i = 0; i < N; i++) {

            if (nums[i] == 0) {

                swap(nums, i, smallEdge++);

            } else if (nums[i] == 2) {

                swap (nums, i, bigEdge--);

                N-=1;

                i -= 1;

            }

        }

    }

    private void swap (int[] nums, int R, int L) {

        int cur = nums[R];

        nums[R] = nums[L];

        nums[L] = cur;

    }

}

巴特西

leecode75. 颜色分类

75. 颜色分类

最新文章

热门文章