经典排序相关面试题
该文章总结自牛课网的在线算法课程(https://www.nowcoder.com/)
经典排序算法就是前面讲那几个（可以看我之前写的关于经典排序的文章哦~）
经典排序（一）
经典排序（二）堆排序
经典排序（三）计数排序和基数排序
一般不能说某个算法就是最快的，要看实际应用情况。工程上一般是多种算法结合使用。下面贴几道和排序有关的经典问题和解法，题目来自牛课网。
我在写解答时候尽量把思路解释清楚再贴代码，并且在给出最优解（我认为的）之前有一个优化的过程。因为在面试或在线做题时候，对于我这样的学渣，突然拿到一个陌生题的时候很难一下子想到最优解，此时可以先把最先想到的方法写出来，然后（在面试官的提醒下）再逐步优化到满足要求的复杂度。我觉得即使没一下子做出来，这样也能体现自己解决问题的能力，还能有一个顺畅的沟通过程（满足面试官装逼的需求。。嘿嘿）。好吧。。。以上都是我胡扯的😂，能直接做出来当然是最好的。下面直接看题吧。
一、小范围排序问题
问题：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。
测试样例：
[2,1,4,3,6,5,8,7,10,9],10,2
返回：[1,2,3,4,5,6,7,8,9,10]
思路：
首先，因为不知道输入值的范围，所以计数排序不考虑。而冒泡排序和选择排序和输入序列是否有序无关，也不是最好选择。。。
其实很容易想到插入排序是个不错的选择，因为之前讲插入排序希尔排序时候都提到过，插入排序在几乎有序情况下很好，接近线性时间。本题说每个元素移动的距离可以不超过k，也就意味着每个元素插入过程中比较交换次数不会超过k，所以用插入排序时间复杂度可以到O（n*k）。
那么有没有更好的解决方法呢？我们接下来考虑一下O（nlogn）级别的那几个算法有没有合适的。
快排归并和输入序列是否有序也没有关系，那堆排序呢？其实这道题的最优解就是利用堆排序的思想做的，算是一个修改过的堆排吧。用下面这个数组举个例子。假设n=8，k=2，输入为下面数组。
输入数组
可以看出来最小元素一定在前3个位置（k+1），所以我们可以建立一个大小为3的最小堆，先把前三个元素插入，再删除最小根并放在第一个位置，然后插入第四个元素，弹出最小根放到第二个位置，依次进行直到结束。每次插入删除操作为O（logk），执行n次，所以这种方法可以做到时间复杂度O（nlogk）。下面是我写的代码。其实应该单独写一个Heap类，然后把堆的各种方法封装起来，这样更符合java规范。如果懒得自己写Heap类，在线题也可以直接使用现成的优先队列。毕竟我们是在用java，别弄得好像还在用c做题一样。我这个代码是偷懒把之前的代码拷贝过来改了改，写的很乱，大家看看就好。
解答：
package fuckingtest;
import java.util.*;
public class ScaleSort {
public int[] sortElement(int[] A, int n, int k) {
int[] heap=new int[k+1];
for(int i=0;i<k+1;i++)
insert(heap,i,A[i]);
for(int i=0,count=k;i<n;i++){
A[i]=delete(heap,count--);
if(i+k+1<n){
insert(heap,++count,A[i+k+1]);
}
}
return A;
}
void insert(int[] A, int count, int data){
int i,temp;
i=count;
A[i]=data;
while(i!=0&&(i-1)/2>=0&&A[(i-1)/2]>data){
temp=A[i];
A[i]=A[(i-1)/2];
A[(i-1)/2]=temp;
i=(i-1)/2;
}
}
void down(int[] A,int count,int i){
int r,l;
int maxson=-1;
for(;;){
l=2*i+1;
r=2*i+2;
if(r<=count){
if(A[l]<A[r])
maxson=l;
else
maxson=r;
}
else if(l<=count&&r>count)
maxson=l;
else if(l>count)
break;
if(A[maxson]<A[i]){
int temp=A[i];
A[i]=A[maxson];
A[maxson]=temp;
i=maxson;
}
else
break;
}
}
int delete(int[] A, int count){
if(count==-1)
return -1;//当堆为空时，报错
int data = A[0];
A[0]=A[count];
A[count--]=0;
down(A,count,0);
return data;//返回删除的值
}
public static void main(String[] args) {
int[] r=new int[10];
int[] a=new int[]{3,1,2,6,5,4,7,8,10,9};
ScaleSort h = new ScaleSort();
r = h.sortElement(a,10,2);
for(int t:r){
System.out.println(t);
}
}
}
二、重复值判断问题
问题：
请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
给定一个int数组A及它的大小n，请返回它是否有重复值。
测试样例：
[1,2,3,4,5,5,6],7
返回：true
思路：
拿到这个题目，我首先想到的是计数排序，简单高效。实际上如果没有额外空间复杂度的限制，我们应该用哈希表来做这道题（如果你不清楚哈希表，上次我实现的计数排序其实就差不多，你可以暂时把它们当一个东西理解）。用哈希表遍历一般数组，记录数值出现次数。时间复杂度和额外空间复杂度都是O（n）。
因为这里有空间复杂度限制，然后我想到可以用二重循环，逐个检查各元素是否有重复值。
boolean cheak(int A[] ,int n ){
for(int i=0; i<n ;i++)
for(int j=i+1; j<n; j++)
if(A[i]==A[j])
return ture;
return false;
}
额外空间复杂度O（1），时间复杂度O（n²）
能不能优化呢？答案是肯定的。一般看到复杂度O（n²）O（n³）这样都是有优化空间的。我们可以利用排序，对数组排序后再进行一次遍历比较相邻元素有没有重复的。先排序，后判断，判断过程变成O（n），现在就是看在原地排序算法里那个时间复杂度最低了。现在我们就知道，应该选取堆排序来处理排序过程啦~（不知道的同学看我前面的文章哦）
不过需要注意的是，书上给出的堆排序经典实现使用的是递归的方式。递归虽然方便理解，但是递归需要用栈保存函数，空间大小是O（logn），所以需要自己写非递归的堆排。下面是我的实现，这个代码只写了接口实现，没写测试。
代码：
import java.util.*;
public class Checker {
public boolean checkDuplicate(int[] a, int n) {
heapSort(a,n);
for(int i =0;i<n-1;i++){
if(a[i]==a[i+1])
return true;
}
return false;
}
public void heapSort(int[] A, int n) {
int count=n-1;
build(A,count);
for(;count>0;){
int temp = A[0];
A[0]=A[count--];
down(A, count,0);
A[count+1]=temp;
}
}
void build(int[] A,int count){
for(int i=(count-1)/2;i>=0;i--){
down(A,count,i);
System.out.println(i);
}
System.out.println("建堆ok：");
for(int t:A){
System.out.println(t);
}
System.out.println(" ");
}
void down(int[] A,int count,int i){
int r,l;
int maxson=-1;
for(;;){
l=2*i+1;
r=2*i+2;
if(r<=count){
if(A[l]>A[r])
maxson=l;
else
maxson=r;
}
else if(l<=count&&r>count)
maxson=l;
else if(l>count)
break;
if(A[maxson]>A[i]){
int temp=A[i];
A[i]=A[maxson];
A[maxson]=temp;
i=maxson;
}
else
break;
}
}
}
三、相邻两数最大差值
问题：
有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。
测试样例：
[1,2,5,4,6],5
返回：2
思路：
这道题感觉有点难度，因为他要复杂度O（n），还要完成排序，然后计算相邻两数最大差值。这需求提的，这不是坑爹嘛¬_¬。
看来常规思路是行不通了。既然如此，只好放大招了，别忘了我们还有一个可以转换时空的超必杀技，用空间换时间之究极计数排序大法！
我首先想到的满足它时间复杂度要求的解决方案就是使用计数排序，因为他要复杂度为O(n)嘛，而我们知道的O（n）级别的算法里也就是计数排序比较灵活了。还是像上次文章里写的一样，用桶排序思想实现。先装桶，再遍历一遍桶，计算非空桶序号最大差值。这个方法时间上满足了，缺点就是计数排序通病，不知道输入值范围，空间需求可会非常大。如果在线做题，时间紧，其实想到这里应该也可以通过大部分测试样例了。反正他也没要求空间复杂度，只要内存不爆炸就可以了。。。
而我看的视频里则给出了更好的方法，下面介绍这种方法，它可以做到时间复杂度空间复杂度都是O（n）。这种方法也是利用了桶排序的思想。我们接着我上面给出的想法往下想。其实桶排序这种思想很灵活，知道输入值范围的时候我们可以根据值大小创建桶（计数排序），而如果这样做桶的数量不可控，我们则可以根据每一位上的数字创建10个桶（基数排序）。
在这个问题里，我们可以只创建n个桶。记输入值最小值min，最大值，max。我们要用n个桶装范围是minmax的n个数，那么每个桶装的范围就是min+ixmin+(i+1)x，x是区间长度，x=（max-min+1）/n。可能这么你不太理解，举个例子就懂了。
假如输入{7，9，3，4，2，1，8}，7个元素。我们把最大值到最小值这个范围等量分成7个区间。换句话说就是要7个区间要能装下1～9的数字，所以每个区间的长度就是9/7，例如第一个区间从1开始范围就是[1,16/7)，第二个区间[16/7,25/7)，以此类推。
接着遍历一遍数组，根据元素的值对应的范围，放到相应的桶里。首先我们知道，会有中间有空桶和没有空桶两种情况。
先考虑没有空桶的情况：
- 这个时候n个数平均分布在n个桶里，这种情况是在输入值增量比较平均的时候，比如输入是{1，5，9}，准备3个桶，区间分别为[1,4)[4,7)[7,10)，每个桶一个元素。这种情况找相邻两数最大差值，只需要比较每个相邻的桶里的元素的差值，找最大的即可。
再考虑有空桶情况：
- n个桶，n个数，有空桶意味着有的桶里不止一个元素。我们知道同一个桶里相邻元素差值小于区间值，而空桶两端的桶里的相邻元素一定大于区间值。也就是说，有空桶的话，相邻两数最大差值处在空桶两端的桶里的相邻元素。这个和我们刚才在计数排序实现的方法里也是一样的，很好理解。
刚刚说了半天，其实就是为了证明，我们完全不用考虑来自同一个桶的相邻元素差值，我们只需要考虑来自不同桶的相邻元素即可。也就是只要比较后一个桶的最小值减去前一个桶的最大值。所以我们只需要记住每个桶里的最大值和最小值，以及后一个桶的最小值和前一个桶的最大值的差值中的最大值即可。装桶过程O（n），遍历桶O（n），两个操作累加，所以时间复杂度O（n）。
写这么久有点累了。。懒得画图，可能直接文字描述有点不太好理解，你可以自己举个例子，画个图，会更好理解一些。下面是我的代码实现。
代码：
package fuckingtest;
import java.util.*;
public class Gap {
public int maxGap(int[] A, int n) {
// write code here
//先找最大值最小值，确定桶范围
int min=A[0];
int max=A[0];
for(int i=0;i<n;i++){
if(A[i]<min)
min=A[i];
if(A[i]>max)
max=A[i];
}
if(max==min)
return 0;
//设x为每个桶的区间长
int x =(max-min)/n;
//定义桶数组B，总共有n个桶，每个桶大小为2，存储该区间内最大值和最小值,然后初始化
int B[][]=new int[n][2];
for(int i=0;i<n;i++){
B[i][0]=-99999;
B[i][1]=-99999;
}
//装桶
for(int i=0;i<n;i++){
int k=getkey(A[i],min,max,n);
if(B[k][0]==B[k][1]&&B[k][0]==-99999)
B[k][1]=B[k][0]=A[i];
if(A[i]>B[k][1])
B[k][1]=A[i];
if(A[i]<B[k][0])
B[k][0]=A[i];
}
for(int i=0;i<n;i++){
System.out.println("min:"+B[i][0]+" max:"+B[i][1]);
}
//比较后一个桶最小值和前一个桶最大值的差值
int r=0;
int temp;
for(int i=0,j=1,f=1;i<n-1;i=i+f){
System.out.println("i:"+i);
j=1;
f=1;
while(B[i+j][0]==-99999){
j++;
f++;
}
System.out.println("j:"+j);
temp=B[i+j][0]-B[i][1];
if(temp>r)
r=temp;
}
return r;
}
int getkey(int v,int min,int max,int n){
return (int)(v-min)*n/(max-min+1);
}
public static void main(String[] args) {
int r;
int[] a=new int[]{1,2,3,6,7,8};
Gap h = new Gap();
r = h.maxGap(a,6);
System.out.println(r);
}
}
四、有序数组合并
问题：
有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。
给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。
思路：
这道题很简单，就是一个归并的过程。和归并排序里面的归并函数做法基本一样，但需要注意的是，这道题是把数组B加入到数组A里。我们需要从后往前比较、加入，这样防止覆盖掉数组A前面的有用部分。过程大致为我们每次从两个列表后面元素选取较大的一个，放入A最后，直到某一个列表到达头部，再将另一个剩下部分逆序取出。时间复杂度O（n+m），空间O（1）。
代码：
import java.util.*;
public class Merge {
public int[] mergeAB(int[] A, int[] B, int n, int m) {
// write code here
int i=n-1;
int j=m-1;
int k=m+n-1;
for(;i>=0&&j>=0;){
if(A[i]>B[j])
A[k--]=A[i--];
else
A[k--]=B[j--];
}
while(i>=0){
A[k--]=A[i--];
}
while(j>=0){
A[k--]=B[j--];
}
return A;
}
}
五、三色排序
问题：
有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。
测试样例：
[0,1,1,0,2,2],6
返回：[0,0,1,1,2,2]
思路：
这是一个经典的荷兰国旗问题，处理过程和快排的划分过程相似，可以参考快排的划分技巧。时间复杂度O（n），空间O（1）。过程为：
遍历数组之前，在数组左端设立“0区”，初始大小0，在数组右端设立“2区”，初始大小0。遍历数组，如果是1，直接跳到下一个；如果是0，把当前元素与“0区”后一位交换，“0区”大小+1，遍历下一个元素；遇到2，把当前元素与“2区”前一位交换，“2区”大小+1，由于“2区”元素并没有遍历过，所以不跳到后一个位置，继续遍历该位置元素。
其实拿到这个问题我最先想到的是用计数排序处理，只要三个桶，几乎可以认为是原地的，简单多了。但这里明确说要用交换，而不是计数。在在线课程下面的评论区里，有小伙伴提出和我一样的疑问，老师的回答是，
如果数组里面放的不是int，long这种类型，而是具体一个一个实例呢？你还能压缩在一起吗？比如数组里面放的是“人”这个类的实例，每个实例有一个“身高”的数据项，请把小于160放左边，160~170放中间，170以上放右边。荷兰国旗问题重点介绍的是一种处理数组的技巧。这种技巧从快排中来，掌握了可以解决很多类似的问题。我并不是在强调这么做才对，只是一种技巧而已。
代码：
public class ThreeColor {
public int[] sortThreeColor(int[] A, int n) {
// write code here
int i=-1;
int j=n;
int temp;
for(int k=0;k<j;){
if(A[k]==0){
swap(A,++i,k++);
}
else if(A[k]==2){
swap(A,--j,k);
}
else
k++;
}
return A;
}
void swap(int A[],int a,int b){
int temp=A[a];
A[a]=A[b];
A[b]=temp;
}
}
六、最短子数组问题
问题：
对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。
测试样例：
[1,4,6,5,9,10],6
返回：2
思路：
拿到这道题，我最直接的想法就是先排序，再比较排序后的数组有变化的位置，位置有变化的元素里的最左的一个到最右的一个，这之间的数组就是题目要求的需要排序的最短子数组。这种方法需要额外空间复杂度O（n），用来保存排序后的数组（或者保存原数组各元素下标情况，这取决于具体实现）。时间复杂度O（nlogn）。
由上面的这个思路，我们可以想到，其实只要知道，需要调整的元素里最右的元素和最左的元素的位置，就可以得到需要排序的最短子数组的长度。我们知道，如果是有序数组，一定是越往右，数值越大，越往左，数值越小，不满足这个条件的元素，那么就是需要调整的元素。于是可以想到下面的这种处理方法。它可以做到时间复杂度O（n），额外空间复杂度O（1）。处理过程大致为：
- 先向右遍历，记住遍历过的元素中的最大值max。如果遍历的当前元素i的值A[i]小于max，说明i是需要向左调整的，记住它。向右遍历，只记录需要向左调整的元素的最右的一个，记为R。
- 再从右至左遍历一次，这次记住遍历过的元素中的最小值min。同理，如果遍历的当前元素i的值A[i]大于min，说明i是需要向右调整的，记住它。遍历过程只记录要调整的最左的一个元素，记为L。
- A[l]~A[R]就是需要排序的最短子数组，它的长度是R-L+1.
代码：
public class Subsequence {
public int shortestSubsequence(int[] A, int n) {
// write code here
int r=-1;
int l=0;
//从左至右遍历，记录最右的当前值小于最大值情况
for(int i=0,max=A[0];i<n;i++){
if(A[i]>=max)
max=A[i];
else
r=i;
}
//从右至左遍历，记录最左的当前值大于最小值情况
for(int i=n-1,min=A[n-1];i>-1;i--){
if(A[i]<=min)
min=A[i];
else
l=i;
}
return r-l+1;
}
}
七、有序矩阵查找
问题：
现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。
给定一个int矩阵mat，同时给定矩阵大小nxm及待查找的数x，请返回一个bool值，代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。
测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3,3,10
返回：false
思路：
这道题可以做到时间复杂度O（m+n），额外空间复杂度O（1）。用下面这个矩阵举例说明。
我们从右上角或左下角作为起始位置开始遍历。这么做是因为矩阵行列都是有序的，右上角是行最小，列最大，左下角相反。我们这里选择从右上角开始，假设待查值是3。当前值是5，如果待查值比当前值大，那么往下走一步，因为我们知道这一行当前位置是最大的，左面所有元素都小于该值，就不用考虑；如果待查值更小，那么往左走一步，理由同上；如果相等，返回true。待查值3<当前值5，往左走一步，当前值变成2。重复上面过程，当前值=4。3<4,所以再往左走，现在待查值3=当前值3，返回true。如果直到越界都没找到，则返回false。
代码：
public class Finder {
public boolean findX(int[][] mat, int n, int m, int x) {
// write code here
int i=0;
int j=m-1;
for(;i<n&&j>-1;){
if(mat[i][j]<x)
i++;
else if(mat[i][j]>x)
j--;
else
return true;
}
return false;
}
}
八、总结
我还有本书叫《数据结构与算法经典问题》，上面和排序有关的题还有好多，本来打算再写几道，但题太多实在写不动+_+，也不想写了，因为题总是做不完的（其实因为我好懒。。）。我感觉有牛课网的算法课介绍的这七道题就足够了，而且正如之前所提到的，最重要的并不是做了多少题，记住了多少解法，而是掌握这些处理方式的技巧和思路，并能够解决类似的问题。
