程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode_75_Sort Colors

leetcode_75_Sort Colors

編輯:關於C++

 

 


 

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.


Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.


Could you come up with an one-pass algorithm using only constant space?




方法一:解題思路
e0代表endOfZero; e1代表endOfOne;curId代表當前遍歷的值
從後往前遍歷,循環一遍
當A[curId]=1,交換A[curId]和A[e0],即將1都交換到最後一個0的位置。成功後e0--,最後一個0的位置向前移了一位
當A[curId]=2,交換A[curId]和A[e0],再交換A[e1]和A[e0],即將2都交換到最後一個0的位置,再將2交換到最後一個1的位置。成功後e0--和e1--,最後一個0和1的位置向前移了一位

 

 

//vs2012測試代碼
#include

using namespace std;

#define N 7

class Solution {
public:
    void sortColors(int A[], int n) 
	{
        int e0=n-1 , e1=n-1;
		for(int curId=n-1; curId>=0; curId--)
		{
			if( A[curId] == 1)
			{
				swap( A[curId],A[e0] );
				e0--;
			}
			if( A[curId] == 2)
			{
				swap( A[curId],A[e0] );
				swap( A[e0],A[e1] );
				e0--;
				e1--;
			}
		}
		for(int i=0; i
//方法一:自測Accepted
//reverse travel the array 
//e0代表endOfZero; e1代表endOfOne
//從後往前遍歷,循環一遍
//當A[curId]=1,交換A[curId]和A[e0],即將1都交換到最後一個0的位置。成功後e0--,最後一個0的位置向前移了一位
//當A[curId]=2,交換A[curId]和A[e0],再交換A[e1]和A[e0],即將2都交換到最後一個0的位置,再將2交換到最後一個1的位置。成功後e0--和e1--,最後一個0和1的位置向前移了一位

class Solution {
public:
    void sortColors(int A[], int n) 
	{
        int e0=n-1 , e1=n-1;
		for(int curId=n-1; curId>=0; curId--)
		{
			if( A[curId] == 1)
			{
				swap( A[curId],A[e0] );
				e0--;
			}
			if( A[curId] == 2)
			{
				swap( A[curId],A[e0] );
				swap( A[e0],A[e1] );
				e0--;
				e1--;
			}
		}
		for(int i=0; i
//方法二:記錄各自次數,在原數組重新賦值0,1,2
class Solution {
public:
    void sortColors(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int r = 0, w = 0, b = 0;
        for (int i = 0; i < n; i++) {
            r += A[i] == 0;
            w += A[i] == 1;
            b += A[i] == 2;
        }
        for (int i = 0; i < n; i++) {
            A[i] = i < r ? 0 : i < r + w ? 1 : 2;
        }        
    }
};

//方法三:這都能通過,應該是OJ的bug
class Solution {
public:
    void sortColors(int A[], int n) 
	{
        sort(A,A+n);
    }
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved