[leetcode]Sort Colors

简介:

问题描写叙述:

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.


基本思想:

遍历一遍记录0,1,2的个数,然后利用计数排序写出代码。


代码:

void sortColors(int A[], int n) {  //C++
        int rNum =0,wNum = 0, bNum =0; 
        for(int i = 0; i < n; i++){ 
            if(A[i] == 0) 
                rNum++; 
            else if(A[i] == 1) 
                wNum++; 
            else bNum++; 
        } 
         
        int rBegin = 0;  
        int wBegin = rNum;  
        int bBegin = rNum+wNum; 
         
        //ith element i < rNum  
        for(int i = 0; i < n; i++){ 
            if(i < rNum) 
                A[i] =0; 
            else if(i < n-bNum) 
                A[i] = 1; 
            else A[i] =2; 
        } 
}


one-pass algorithm

void sortColors(int[] A) {


    int i=-1, j=-1, k=-1;

    for(int p = 0; p < A.length; p++)
    {
        if(A[p] == 0)
        {
            A[++k]=2;
            A[++j]=1;
            A[++i]=0;
        }
        else if (A[p] == 1)
        {
            A[++k]=2;
            A[++j]=1;

        }
        else if (A[p] == 2)
        {
            A[++k]=2;
        }
    }

}










本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5059223.html,如需转载请自行联系原作者


相关文章
LeetCode 75 Sort Colors 颜色分类(荷兰国旗)
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
62 0
LeetCode 148. Sort List
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
55 0
LeetCode 148. Sort List
|
索引
LeetCode 75. Sort Colors
给定一个具有红色,白色或蓝色的n个对象的数组,对它们进行就地排序,使相同颜色的对象相邻,颜色顺序为红色,白色和蓝色。 这里,我们将使用整数0,1和2分别表示红色,白色和蓝色。 注意:您不应该使用库的排序功能来解决此问题。
29 0
LeetCode 75. Sort Colors
|
人工智能 C++ Python
LeetCode 905. Sort Array By Parity
LeetCode 905. Sort Array By Parity
64 0
|
vr&ar
【LeetCode1122】数组的相对排序(哈希or自定义sort)
没错,,简单题,就是说将arr1中有arr2的元素,则按照arr2的元素先排列(特别注意:这里的arr2的元素都是不同的,但是arr1中是可以元素重复的)
133 0
【LeetCode1122】数组的相对排序(哈希or自定义sort)

相关产品