[leetcode/Matrix](sort)Sort Colors-计数排序的运用

约定不等于承诺〃 2021-09-28 07:46 350阅读 0赞

### Sort Colors 计数排序 ###

*   *  题干：
     *  第一种解法:计数排序
     *  第二种解法:头尾指针解法

## 题干： ##

Given an array with n objects colored red, white or blue, sort them in-place(the input is overwritten by the output as the algorithm executes) 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.

Example:

Input: [2,0,2,1,1,0]
    Output: [0,0,1,1,2,2]

Please submit a cpp file with the implementation of function`void sortColors(vector<int>& nums)`, you can start like this:

void Solution::sortColors(vector<int>& nums){}

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 a one-pass algorithm using only constant space?

## 第一种解法:计数排序 ##

① 扫描第一遍,找出最大最小数  
② 开辟一个数组a,长度为max-size+1  
③ 扫描第二遍数组,记录每个数字出现的频率即a\[nums\[i\]\]++  
④ 扫描数组a,输出

适用于已经知道最大最小的情况,这是一种牺牲空间的做法

#include"Solution.h"
    #include<algorithm>
    #include<string.h>
    void Solution::sortColors(vector<int>& nums){ 
    	int size=nums.size();
    	int min=1e10;
    	int max=0;
    	
    	for(int i=0;i<size;i++){ 
    		if(nums[i]<min){ 
    			min=nums[i];
    		}
    		if(nums[i]>max){ 
    			max=nums[i];
    		}
    	} 
    	//遍历一遍找出最大最小值 
    	
    	int *a=new int[max-min+1];
    	
    	memset(a,0,(max-min+1)*sizeof(int));
    	
    	for(int i=0;i<size;i++){ 
    		a[nums[i]-min]++;
    	} 
    	
    	int count=0;
    	for(int i=0;i<max-min+1;i++){ 
    		while(a[i]){ 
    			a[i]--;
    			nums[count++]=i+min;
    		}
    	} 
    	
    	delete []a;
    	
    }

## 第二种解法:头尾指针解法 ##

left左边全是0,right右边全是2  
中间是1

#include"Solution.h"
    void Solution::sortColors(vector<int>& nums){ 
    	int left=0;
    	int right=nums.size()-1;
    	
    	int i=0;
    	
    	while(i<=right){ 
    		if(nums[i]==0){ 
    			swap(nums[left],nums[i]);
    			left++;
    			i++;
    		}	
    		else if(nums[i]==2){ 
    			swap(nums[right],nums[i]);
    			right--;
    		}
    		else
    			i++;
    	}
    }
    
    void swap(int &a,int& b){ 
    	int temp=a;
    	a=b;
    	b=temp;
    }