1.荷兰三色国旗问题
问题描述：一个数组只含有三种元素：0，1，2，不使用计数排序，将0放在1的左边，2放在1的右边。
分析：
1.可借鉴快排中划分的思想。将数组分为{0区},arr[],{2区}
2.遍历arr,当发现0时，0区向右扩，发现2时，2区向左扩，
3.当前元素进入2区时，结束。
vector<int> sortThreeColor(vector<int> A, int n) { // write code here int last0=-1; int first2=n; for(int i=0;i<n;i++){ if(i==first2) break; if(A[i]==0){ int temp=A[last0+1]; A[last0+1]=0; last0++; A[i]=temp; } if(A[i]==2){ int temp=A[first2-1]; A[first2-1]=2; first2--; A[i]=temp; i--;//（由于2区换来的数未进行判断，需重新判断一次） } } return A; }
2.行列矩阵查找元素的问题
问题描述：在一个行列都有序的二维矩阵中，找出某个元素。
如矩阵：1 2 3 4 查找元素6
2 3 3 4
3 4 6 7
分析：首先从矩阵右上角开始，如果当前元素e>6,则往左走，即列-1，如果e<6，则往下走，即行+1，否则找到。
如果当前元素下标超出矩阵范围，则找不到。
3.最短未排序子数组
对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。
测试样例：
[1,4,6,5,9,10],6
返回：2
vector<int> sortThreeColor(vector<int> A, int n) { // write code here int last0=-1; int first2=n; for(int i=0;i<n;i++){ if(i==first2) break; if(A[i]==0){ int temp=A[last0+1]; A[last0+1]=0; last0++; A[i]=temp; } if(A[i]==2){ int temp=A[first2-1]; A[first2-1]=2; first2--; A[i]=temp; i--; } } return A; }
4.计算排序后相邻两数的最大差值
问题描述：
有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。
测试样例：
[1,2,5,4,6],5
返回：2
分析：
1.使用基于桶排序的思想对数据进行划分，得到相邻划分区间的最大差值。
步骤：
1.找出max,min。
2.len=max-min。
2.创建N+1个桶，前N个桶存放落于区间 [min+i*len,min+(i+1)*len )内的数组元素。（由于初值是min，间距是len，分析可以就可以算出来）
3.把最大值（可能不止一个）放入最后一个桶内。
4.找出相邻桶相差最大的那个的值。（前一个桶的数组元素的最大值，后一个桶的数组元素的最小值）
附实现代码：
int maxGap(vector<int> A, int n) { // write code here int maxValue,minValue; maxValue=minValue=A[0]; for(int i=1;i<n;i++){ if(A[i]>maxValue) maxValue=A[i]; if(A[i]<minValue) minValue=A[i]; } if(maxValue==minValue) return 0; vector<vector<int> > data(n+1); int len=(maxValue-minValue); for(int i=0;i<n;i++){ if(A[i]==maxValue) data[n].push_back(A[i]); else{ int k=(A[i]-minValue)*n/len; data[k].push_back(A[i]); } } int MaxGap=0; for(int i=0;i<n;i++){ if(data[i].size()==0) continue; else{ int j=i+1; while(data[j].size()==0) j++; int m1=data[i][0],m2=data[j][0]; for(int ii=1;ii<data[i].size();ii++) if(m1<data[i][ii]) m1=data[i][ii]; for(int jj=1;jj<data[j].size();jj++) if(m2>data[j][jj]) m2=data[j][jj]; if(MaxGap<(m2-m1)) MaxGap=m2-m1; } } return MaxGap; }