首页 > 试题广场 >

排列颜色

[编程题]排列颜色
  • 热度指数：15788 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。
我们用0,1,2分别代表颜色红，白，蓝
注意：
本题要求你不能使用排序库函数
扩展：
一个非常直接的解法是两步的计数排序的算法
首先：遍历一遍数组，记录0,1,2的数量，然后重写这个数组，先将0写入，再将1写入，再将2写入
你能给出一个只用一步，并且能在常数级空间复杂度解决这个问题的算法吗？
算法知识视频讲解
添加回答
C/C++
chenlongxi头像 chenlongxi
三路快排的思想，以1作为标志，比1小的放在一边，比1大的放在另一边，但是要注意一点的是大的元素进行交换后由于该元素没有和标志1作比较，因此需要i=i-1。

    void sortColors(int A[], int n) {
    int begin = 0, end = n - 1, lt = 0, gt = n - 1;
    for (int i = 0; i <= gt; ++i)
    {
        if (A[i] < 1)
        {
            A[i] = A[lt]; A[lt] = 0; ++lt;
        }
        else if (A[i] > 1)
        {
            A[i] = A[gt]; A[gt] = 2; --gt;
            i = i - 1;
        }
    }
  }

编辑于 2018-03-20 16:03:44 回复(1)
revivedSuN头像 revivedSuN
荷兰国旗问题。
发表于 2016-06-09 16:46:40 回复(0)
C/C++
F-L头像 F-L 
class Solution {
public:
    void sortColors(int A[], int n) {
        int one = -1;
        int two = n;
        for(int i = 0; i < two; ){
            if(A[i] == 0){
                swap(A[++one], A[i++]);
            }else if(A[i] == 2){
                swap(A[i], A[--two]);
            }else{
                ++i;
            }
        }
    }
};

发表于 2018-03-29 21:47:42 回复(0)
Java
LiberHome头像 LiberHome 
class Solution {
    public void sortColors(int[] nums) {
        //首先形式上：如果是考数组的算法 双指针算是常规套路了。。这个荷兰🇳🇱国旗问题用的三指针
        //其次 本质上 也还是蛮巧妙的。
        int p0, p1, p2, tmp;
        p0 = 0;
        p1 = 0;
        p2 = nums.length - 1;

        while(p1 <= p2){
            if(nums[p1] == 0){
                //如果p1对应的元素是0 交换p0和p1对应的元素,然后向后++一位
                tmp = nums[p0];
                nums[p0++] = nums[p1];
                nums[p1++] = tmp;
            }
            else if(nums[p1] == 2){
                //交换，--
                tmp = nums[p1];
                nums[p1] = nums[p2];
                nums[p2--] = tmp;
            }
            else{
                p1++;
            }
        }
    }
}

发表于 2020-07-15 21:17:44 回复(0)
C/C++
J.Fan头像 J.Fan 
//荷兰国旗问题，基本思路是，遍历数组跟中间值1做比较，主要有以下两步：
//1、设置最后一个连续0的位置索引（从前往后），设置第一个连续2的位置索引（从后往前）
//2、如果遍历到0，就交换，此时不用考虑交换后的ind位置的值（因为如果后面还有0会继续替换），
//如果遇到2，需要与连续2的位置索引交换，但此时ind不能++(因为如果++后面就没有机会和2的索引位置交换值了)
class Solution {
public:
    void sortColors(int A[], int n) {
        int zeroInd = 0,twoInd = n-1;
        for(int ind=0;ind<=twoInd;ind++)
        {
            if(A[ind]==0)
            {
                A[ind] = A[zeroInd];
                A[zeroInd] = 0;
                zeroInd++;
            }else if(A[ind]==2)
            {
                A[ind] = A[twoInd];
                A[twoInd] = 2;
                twoInd--;
                ind--;
            }
        }
    }
};

发表于 2019-01-22 17:08:38 回复(0)
Java
詆調壹點头像 詆調壹點 
public class Solution {
   public void sortColors(int[] A) {
		int begin = 0;
		int end = A.length - 1;
		int cur = 0;
		while (cur <= end) {
			// 所有的0放到数组前边
			if(A[cur] == 0) {
				A[cur] = A[begin] ^ A[cur] ^ (A[begin] = A[cur]);
				begin ++ ;
				cur ++ ;
			// 所有2放到数组后边
			} else if(A[cur] == 2) {
				A[cur] = A[end] ^ A[cur] ^ (A[end] = A[cur]);
				end -- ;
			} else cur ++ ;
		}
	}
}
编辑于 2016-12-03 00:57:45 回复(0)
lollipop😈😈头像 lollipop😈😈 
public class Solution {
    /**
    // 解法一，桶排序
    public void sortColors(int[] A) {
        if (A == null) {
            return;
        }
        int[] count = new int[3]; // 统计1、2、3出现的次数
        for (int num : A) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i < count[0]; i++) {
            A[index++] = 0;
        }
        for (int i = 0; i < count[1]; i++) {
            A[index++] = 1;
        }
        for (int i = 0; i < count[2]; i++) {
            A[index++] = 2;
        }
    }
    */    
    
    // 解法二，三路快排
    public void sortColors(int[] A) {
        if (A == null) {
            return;
        }
        int zero = -1;// 保证[0, zero]区间内为0
        int two = A.length;// 保证[two, nums.length - 1]区间内为2
        for (int i = 0; i < two;) {
            if (A[i] == 0) {
                A[i++] = A[++zero];
                A[zero] = 0;
            } else if(A[i] == 2) {
                A[i] = A[--two];
                A[two] = 2;
            } else {
                i++;
            }
        }
    }
}
发表于 2019-01-27 12:32:06 回复(0)
啦啦啦18头像 啦啦啦18 
class Solution {
public:
    void sortColors(int A[], int n) {
        int low=0,mid=0,hi=n-1;
        while(mid<=hi){
            if(A[mid]==0) swap(A[mid++],A[low++]);
            else if(A[mid]==1) ++mid;
            else if(A[mid]==2) swap(A[mid],A[hi--]);
        }
    }
};

发表于 2018-08-27 12:57:26 回复(0)
向程序猿进化头像 向程序猿进化
//数组中只有0，1,2.排序不允许使用辅助空间。只能遍历一次
/*思路：用zeroIndex来表示放置0的索引，元素是0就将其往前面放(利用交换两个元素的位置，实现把0往前放)
 * 同理用twoIndex来表示放置2的索引，元素是2就将其往后面放(利用交换两个元素的位置，实现把2往后放)
 * 
 * */
public class Solution {
   public void sortColors(int[] A) {
        if (A == null || A.length < 2) {
            return;
        }
        int zeroIndex = 0;
        int twoIndex = A.length - 1;
            int i=0;
        while (i < A.length && twoIndex > zeroIndex) {
            if (A[i] == 0) {
                swap(A, i, zeroIndex);
                zeroIndex++;
                i++;
            }
            else if (A[i] == 2) {
                if(i>=twoIndex) return ;//twoIndex记录的是2的索引，twoIndex后面的都是2，不用再排了
                swap(A, twoIndex, i);
                twoIndex--;
            } else {
                i++;
            }
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }
}

发表于 2018-05-05 13:28:37 回复(0)
页川先生头像 页川先生 
思路1:桶排序
void sortColors(int A[], int n) {
        if(A==NULL||n<=0)
            return;
        vector<int> count(3,0);
        for(int i=0;i<n;i++){
            count[A[i]]++;
        }
        int index=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<count[i];j++){
                A[index++]=i;
            }
        }
    }


思路2:双指针遍历
void sortColors(int A[], int n) {
        if(A==NULL||n<=0)
            return;
          int left=0;
        int right=n-1;
        int i=left;
        while(i<=right){
            if(A[i]==0){
                swap(A[i],A[left]);
                i++;
                left++;
            }
            else if(A[i]==1){
                i++;
            }
            else{
                swap(A[i],A[right]);
                right--;
            }
        }
    }

发表于 2017-11-06 09:54:02 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    void sortColors(int A[], int n) {
        int start=0,end=0;
        for(int i=0;i<n-end;i++)
        {
        	if(A[i] == 0)
        	{
        		swap(A[i],A[start]);
				start++;        		
			}else if(A[i] == 2){
				swap(A[i],A[n-1-end]);
				end++;
				i--;
			}
		}
    }
};

发表于 2017-07-29 18:29:40 回复(0)
sky_头像 sky_ 
/*1.当遇到一个0时，我们就与pos0位置上的数字交换，这样就能保证左边一路全都是0，
并且因为2已经与pos2交换了，pos0位置与当前i之间只能是全1，所以pos0上的只会是1.
2.当遇到一个2时，我们就与pos2交换，然后再重新判断下现在位置上的值。
3.需要i<=pos2否则会进行错误的继续交换。
*/class Solution {
public:
    void sortColors(int A[],int n) {
         int pos0=0,pos2=n-1;
         for(int i=0;i<n&&i<=pos2;i++){
             if(A[i]==0) swap(A[i],A[pos0++]);
             else if(A[i]==2) swap(A[i--],A[pos2--]);
         }
    }
};

编辑于 2017-07-29 13:29:46 回复(0)
ahac头像 ahac 
class Solution {
public:
    void myswap(int &a, int &b){
        int t = a;
        a = b;
        b = t;
	}
    void sortColors(int A[], int n) {
        int l = 0;
        int r = 0;
        for (int i = 0; i < n-r; i++){
            if (A[i] == 0){
                myswap(A[i], A[l]);
                l++;
            }
            else if(A[i]==2){
                myswap(A[i], A[n - 1 - r]);
                r++;
                i--;
            }
        }
    }
};

发表于 2016-05-18 19:42:21 回复(0)
JacobGo！头像 JacobGo！ 
/*
* 桶排序的应用。
* 类似于剑指offer中的年龄排序问题
* 时间复杂度O(n)
* 空间复杂度O(n)
* 很经典的牺牲空间换时间的解法
* leetcode测试结果：Runtime: 0 ms.Your runtime beats 61.03 % of java submissions.
*/
public void sortColors(int[] nums) {
		int[] count = new int[3];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == 0)
				count[0]++;
			else if (nums[i] == 1)
				count[1]++;
			else
				count[2]++;
		}
		int index = 0;
		for (int i = 0; i < count[0]; i++) {
			nums[index++] = 0;
		}
		for (int i = 0; i < count[1]; i++) {
			nums[index++] = 1;
		}
		for (int i = 0; i < count[2]; i++) {
			nums[index++] = 2;
		}

	}

发表于 2017-06-29 10:54:51 回复(2)
C/C++
华科平凡头像 华科平凡

C++ solution:

使用sort函数。

#include <algorithm>
using namespace std;
class Solution {
public:
    void sortColors(int A[], int n) {
        sort(A,A+n);

    }
};
发表于 2017-10-27 17:14:32 回复(0)
C/C++
向宇左桌头像 向宇左桌
题目说的one-pass看到很多人还是用sort或者是用题目提示的那种two-pass解决，实在是尴尬
我的思路如下：
设置3个变量，分别代表数组前部zeroindex，当前遍历的位置 i，数组后部 twoindex
①当A[i] = 0时，必然属于数组前部，则交换A[i] 和 A[zeroindex] ,接着i++ , zeroindex++
②当A[i] = 1时，只需i++就好，因为只有排好了0和2,1自然就只能在中间了，故不作处理
③当A[i] = 2时，不然属于数组后部，则交换A[i]和A[twoindex]，接着twoindex--，不过此时就不能i++了因为，交换过去的A[i]有可能是0或者2，所以需要在下一个循环里判断，这样它的位置才能够正确 
class Solution {
public:
    void sortColors(int A[], int n) {
        int zeroindex = 0;
        int twoindex  = n - 1;
        int i = 0;
        while(i < twoindex + 1)
        {
        	if(A[i] == 0)
            {
            	swap(A[i],A[zeroindex]);
                zeroindex++;
                i++;
            }
            else if(A[i]==2)
            {
            	swap(A[i],A[twoindex]);
                twoindex--;
            }
            else
                i++;
        }
    }
};

发表于 2017-01-11 12:37:38 回复(5)
C/C++
祈嗻头像 祈嗻
class Solution {
public:
    void sortColors(int A[], int n) {
        int i = 0, j = 0, k = n - 1, temp;
        while(j <= k){
            if(A[j] == 0){//红
                temp = A[j];
                A[j] = A[i];
                A[i] = temp;
                i++;
                j++;
            }
            else if(A[j] == 2){//蓝
                temp = A[j];
                A[j] = A[k];
                A[k] = temp;
                k--;
            }
            else{//白
                j++;
            }
        }
    }
};
编辑于 2024-01-02 17:34:44 回复(0)
Java
男神20190129221786头像 男神20190129221786 
public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length < 2)
            return;
        int l = -1;//0区的右边界
        int r = A.length;//2区的左边界
        int m = 0;//1区的右边界
        while(m < r){//当1区右边界和2区左边界相遇时停
            if(A[m] == 0){
                swap(A, ++l, m++);
            }else if(A[m] == 2){
                swap(A, m, --r);
            }else{//A[m] == 1
                m++;
            }
        }
    }
    
    public void swap(int[] arr, int i, int j){
        if(i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

发表于 2021-09-08 21:58:06 回复(0)
牛客409004206号头像 牛客409004206号 
// var arr= read_line()
var arr = [2,1,0];
var res = [];
var index = -1;
var index1=-1
var index2=-1
var len = arr.length - 1;
while (len >= 0) {
    // console.log(arr.indexOf(2,index2+1),'9',index2)
    // console.log(arr.indexOf(2, index2 + 1)!== -1,index2, arr.indexOf(0, index2 + 1));
  if (arr.indexOf(0, index + 1) > -1 && index !== arr.indexOf(0, index + 1)) {
    index = arr.indexOf(0, index + 1);
    // console.log('0')
    res.push(0);
  } 
  else if(arr.indexOf(1, index1 + 1) > -1 && index1 != arr.indexOf(1, index1 + 1)){
    index1 = arr.indexOf(1, index1 + 1);
    // console.log('1')
    res.push(1);
  } else if(arr.indexOf(2, index2 + 1) > -1 && index2 != arr.indexOf(2, index2 + 1)){
    index2 = arr.indexOf(2, index2 + 1);
    // console.log('2')
    res.push(2);
  }

  len--;
}



console.log('['+res+']');

发表于 2021-09-02 15:21:28 回复(0)
C/C++
牛客770040937号头像 牛客770040937号 
class Solution {
public:
    void sortColors(int A[], int n) {
        sort(A,A+n);
    }
};


发表于 2020-12-30 09:52:51 回复(0)
提交观点

问题信息

数组
难度：
73条回答 23394浏览

热门推荐

通过挑战的用户

查看代码

相关试题

排列颜色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号