第13节 小范围排序练习题
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过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个里面，这样可以考虑用一个小顶堆，大小正好为k，每次把堆顶的元素弹出，在把新的元素（后一个元素）加入，一直到剩下最后k个元素，再利用堆排序对剩下的k个元素即可。 class ScaleSort {public: vector<int> sortElement(vector<int> A, int n, int k) { // 边界检测 if(A.size()==0 || n<1 || k<0|| k>n){ return A; } //初始化小顶堆 vector<int> minHeap(k); for(int i=0;i<k;i++){ minHeap[i] = A[i]; } for(int i=k/2;i>=0;i--){ adjustHeap(minHeap,i,k); } //使用小顶堆，求出前n-k个值 for(int i=0;i<n-k;i++){ A[i] = minHeap[0]; minHeap[0] = A[i+k]; adjustHeap(minHeap,0,k); } //对剩余的k个值，使用堆排序 for(int i=n-k;i<n;i++){ A[i] = minHeap[0]; swap(minHeap[0],minHeap[k-1]); adjustHeap(minHeap,0,--k); } return A; } //调节parent -> n 的数组元素 void adjustHeap(vector<int> &heap,int parent,int n){ if(parent>n){ return; } int tmp = heap[parent]; int min_child = 2*parent+1; while(min_child<n){ if(min_child+1<n && heap[min_child+1]<heap[min_child]){ min_child++; } if(tmp<=heap[min_child]){ break; } heap[parent] = heap[min_child]; parent = min_child; min_child = 2*parent+1; } heap[parent] = tmp; }};
第14节 重复值判断练习题 请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
给定一个int数组A及它的大小n，请返回它是否有重复值。
测试样例：[1,2,3,4,5,5,6],7返回：true思路1：排序后前后对比（AC代码）class Checker {public: bool checkDuplicate(vector<int> a, int n) { // write code here sort(a.begin(),a.end()); for(int i=0;i<a.size()-1;++i){ if(a[i]==a[i+1]){ return true; } } return false; }};
第15节 有序数组合并练习题
有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。
给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。思路：两个指针分别指向数组有效数字的末尾， 然后再向前对比大小，谁大谁放在后面。最后把剩余的那一部分copy过去即可。class Merge {public: int* mergeAB(int* A, int* B, int n, int m) { // write code here int i=n-1,j=m-1; int cur = m+n-1; while(i>=0&&j>=0){ if(A[i]>B[j]) { A[cur]=A[i]; cur--; i--; } else{ A[cur]=B[j]; cur--;j--; } } while(i>=0){ A[cur--]=A[i--]; } while(j>=0){ A[cur--]=B[j--]; } return A; }};
17，三色排序练习题
有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0，1，2的整数数组A及它的大小，请返回排序后的数组。保证数组大小小于等于500。
测试样例：[0,1,1,0,2,2],6返回：[0,0,1,1,2,2]
荷兰国旗问题思路1：计数排序，扫描一遍过去，分别记录0，1，2的个数，然后再对数组进行赋值。时间复杂度为O(2n)，即O(n)，满足条件。 很蠢的方法。class ThreeColor {public: vector<int> sortThreeColor(vector<int> A, int n) { // write code here int num1=0,num2=0,num3=0; for(int i=0;i<n;i++){ if(A[i]==0) num1++; else if(A[i]==1) num2++; else if(A[i]==2) num3++; } for(int i=0;i<num1;i++) A[i] = 0; for(int i=num1;i<num1+num2;i++) A[i] = 1; for(int i=num1+num2;i<num1+num2+num3;i++) A[i] = 2; return A; }};
思路2： 基于快速排序的交换，用两个指针记录两个区域的位置（0区域和2区域），详细参考http://blog.csdn.net/s634772208/article/details/46740191用一个变量遍历数组，数值为1时跳过，为2时和后面的（p2指针）交换，为0时和前面的（p1指针）交换。
class ThreeColor {public: vector<int> sortThreeColor(vector<int> A, int n) { // write code here int p1 = 0,p2 = n-1; int i=0; while(i<=p2){ if(A[i]==2){ swap(A,i,p2); p2--; } else if(A[i]==0 && i>p1){ swap(A,i,p1); p1++; } else{ i++; } } return A; } void swap(vector<int> &A,int i,int j){ int temp=A[i]; A[i]=A[j]; A[j]=temp; }};第18节 有序矩阵查找练习题
现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值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思路：根据矩阵递增的特点来做此道题目，关键是从矩阵的右上角来进行查找，若数值比要查找的数大，则删除该列，若数值查找的数小，则删除改行。class Finder {public: bool findX(vector<vector<int> > mat, int n, int m, int x) { // write code here if(m <= 0 || n <= 0){ return false; } int row = 0; int col = m -1; while(row<n && col>=0){ if(mat[row][col]==x){ return true; }else if(mat[row][col]>x){ col--; } else if(mat[row][col]<x){ row++; } } return false; }};
第19节 最短子数组练习题
对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。
测试样例：[1,4,6,5,9,10],6返回：2思路：题目的意思很难搞清楚，我的理解是找到一段序列中需要排序的起始位置和终止位置即可。 其中中间有序的部分也算进去。比如 比如1 3 4 7 6 8 9 3 2 0 10 12 的输入，最短子数组是 7 6 8 9 3 2 0 而不是其中一段如 7 6（因为8 9 是有序的）需要向前遍历记录最右边的位置，再向右遍历记住最左边的位置，注意分别用两个变量记录有序的部分（max 向前时记录，min 向后时记录）
class Subsequence {public: int shortestSubsequence(vector<int> A, int n) { // write code here if(n<=0) return 0; int left=n-1; // 向左移动的位置指针 int right=0; //向右移动的位置指针 int max=A[0]; //记录当前的最大值 int i,j; for( i=0;i<n;++i){ if(A[i]>=max){ max = A[i]; }else{ right = i; } } int min = A[n-1]; for( j=n-1;j>=0;--j){ if(A[j]<=min) min = A[j]; else left =j; } if(left==n-1&right==0) return 0; return (right-left+1); }};
20 相邻两数最大差值练习题
有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。
测试样例：[1,2,5,4,6],5返回：2思路：如果用排序法实现，其时间复杂度为O(NlogN)，而如果利用桶排序的思想（不是桶排序），可以做到O(N)，额外空间复杂度为O(N)。遍历arr找到最大值max和最小值min。如果arr的长度为N，准备N+1个桶，把max单独放在第N+1个桶中，[min,max)范围上的数放在1~N号桶里，对于1~N号桶中的每一个桶来说，负责的区间为(max-min)/N。如果一个数为num，它应该分配进(num-min)*len/(max-min)。arr一共有N个数，旻、一定会放进1号桶中，max一定会放进最后的桶中，所以，如果把所有的数放进N+1个桶中，必然有桶是空的。产生最大差值的相邻数来自不同桶。所以只要计算桶之间数的间距可以，也就是只用记录每个桶的最大值和最小值，最大差值只可能来自某个非空桶的最小值减去前一个非空桶的最大值。看了别人写的一个代码，太好了，直接copy 学习了
class Gap {public: int maxGap(vector<int> A, int n) { // write code here int minValue=A[0],maxValue=A[0]; for(int i=1;i<n;i++){ if(A[i]>maxValue) maxValue=A[i]; if(A[i]<minValue) minValue=A[i]; } //算出桶的值最大最小值 vector<int> bocketMax(n,INT_MIN); //初始化 vector<int> bocketMin(n,INT_MAX); int len=maxValue-minValue; if(len<1) return 0; for(int i=0;i<n;i++){ int index=(double)(A[i]-minValue)/len*(n-1); bocketMax[index]=max(A[i],bocketMax[index]); // 存放较大的值 bocketMin[index]=min(A[i],bocketMin[index]); //存放较小的值 } int res=0,pre=bocketMax[0]; //最大间隔值为前一个桶的最大值与后一个桶的最小值的差值。 for(int i=1;i<n;i++){ if(bocketMin[i]!=INT_MAX){ //保证桶不为空 res=max(res,bocketMin[i]-pre); pre=bocketMax[i]; } } return res; }}
参考1，百度百科2，大话数据结构