面试题 16.16. 部分排序-双指针法
2023-09-14 09:06:53 时间
面试题 16.16. 部分排序
给定一个整数数组,编写一个函数,找出索引m和n,只要将索引区间[m,n]的元素排好序,整个数组就是有序的。注意:n-m尽量最小,也就是说,找出符合条件的最短序列。函数返回值为[m,n],若不存在这样的m和n(例如整个数组是有序的),请返回[-1,-1]。
示例:
输入: [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出: [3,9]
解题代码如下:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* subSort(int* array, int arraySize, int* returnSize){
int low=0,high=arraySize-1;
int *re=(int *)malloc(sizeof(int)*2);
re[0]=-1;
re[1]=-1;
*returnSize=2;
if(arraySize<=1){
return re;
}
while(array[low]<=array[low+1]){
low++;
// printf("%d ",low);
if(low==arraySize-1){
return re;
}
}
while(array[high-1]<=array[high]){
high--;
if(high==0){
return re;
}
}
// printf("low high %d %d",low,high);
int i;
int min=999,max=-1000;
for(i=low;i<=high;i++){
if(array[i]<min){
min=array[i];
}
if(array[i]>max){
max=array[i];
}
}
// printf("min max %d %d",min,max);
while(array[low]>min){
if(low==0){
break;
}
low--;
if(low==0){
break;
}
}
while(array[high]<max){
if(high==arraySize){
break;
}
high++;
if(high==arraySize){
break;
}
}
if(low==0){
low--;
}
re[0]=low+1;
re[1]=high-1;
*returnSize=2;
return re;
}