面试题 16.16. 部分排序-双指针法

面试题 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;

    
}