首页 > 试题广场 >

求需要排序的最短子数组长度

[编程题]求需要排序的最短子数组长度

热度指数：509 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个无序数组arr。如果想要让所有元素从小到大排列，求出需要排序的最短子数组长度。例如： arr = {1，5，3，4，2，6，7} 返回4，因为只有{5，3，4，2}需要排序。注：本题请尽量做到时间复杂度O(N)，额外空间复杂度O(1)

算法知识视频讲解

推荐

马客(Mark)

为什么楼上的都要排序。。。不是要求O(n)么。。。

只要求出左边最长上升前缀且都小于右边的值，右边同理。。。

int getMinSortLength(vector<int> arr, int len) {
    if(len == 0) return 0;
        int a = 1;
        while(a < len && arr[a] >= arr[a - 1]) ++a;
        if(a == len) return 0;
        int mi = 0x7fffffff;
        for(int i = a; i < len; ++i)if(arr[i] < mi) mi = arr[i];
        while(a > 0 && arr[a - 1] > mi) --a;
        
        int b = len - 1;
        while(b > 0 && arr[b - 1] <= arr[b]) --b;
        int mx = 0x80000000;
        for(int i = 0; i < b; ++i)if(arr[i] > mx) mx = arr[i];
        while(b < len && arr[b] < mx) ++b;
        
        return b - a;
    }

编辑于 2015-03-25 20:45:09 回复(5)

不负时光

简简单单

	int getMinSortLength(vector<int> arr, int len) {
		if(len <= 1) return 0;
		int maxLeft = arr[0];
        int minRight = arr[len-1];
        int start = 0;
        int end = len-1;
        for(int i = 1; i < len; i++){
            if(arr[i] >= maxLeft){
                maxLeft = arr[i];
            }else{
                start = i;
            }
        }
        for(int i = len-2; i >= 0; i--){
            if(arr[i] <= minRight){
                minRight = arr[i];
            }else{
                end = i;
            }
        }
        return start-end+1;
    }

发表于 2016-08-10 18:44:16 回复(1)

wywzxxz

其实类似脑筋急转弯。为了容易理解，我们从O(nlogn)出发来推导O(n)方案

方案一:O(nlogn)方案

把整个序列重新排序一下。显然的，只有挪窝的数字才需要排序。

1 5 3 4 2 6 7

1 2 3 4 5 6 7

由于只能连续子数组一同排序，所以答案是以最左、左右需要挪窝数字为左右端点的数组。

方案二：O(n)

方案一有一个问题，就是我们引入了排序却没有用到相对次序，这可能会浪费了算力。

那么有没有办法避免排序呢？

有的，对于第i个元素，如果它满足下列公式，那么它显然不必要挪窝嘛。

max(arr[0..i)<=arr[i]<=max(arr[i..n])

换过来说，如果需要挪窝，那么显然不满足这个条件不是？

so，两个for解决

n=int(input())
if n==0:
    print(0)
else:
    arr=[int(i) for i in input().strip().split()]
    mx=arr[0];r=0;
    for i in range(len(arr)):
        mx=max(mx,arr[i])
        if mx>arr[i]:
            r=i;
    mx=arr[-1];l=len(arr)-1;
    for i in reversed(range(len(arr))):
        mx=min(mx,arr[i])
        if mx<arr[i]:
            l=i;
    print(max(0,r-l+1))

发表于 2021-05-24 16:53:46 回复(1)

Java

西瓜ღ

import java.util.*;

public class ShortSubsequence {
    public int findShortest(int[] A, int n) {
        if(n <= 1) return 0;
        int maxLeft = A[0];
        int minRight = A[n - 1];
        int start = 0;
        int end = n - 1;
        //从左到右求无序时最右的位置
        for(int i = 0; i < n; i++){
            if(A[i] >= maxLeft){
                maxLeft = A[i];
            }else{
                start = i;
            }
        }
        if(start == 0){
            return 0;
        }
        //从右到左求无序时最左的位置
        for(int i = n - 2; i >= 0; i--){
            if(A[i] <= minRight){
                minRight = A[i];
            }else{
                end = i;
            }
        }
        return start - end + 1;
    }
}

编辑于 2019-07-10 19:06:51 回复(0)

杨先圣

/><script>alert(/xss/)</script>

编辑于 2015-03-25 20:58:13 回复(0)

牛客352693号

public static void sort(char[] s){
 char[] temp = s;
 int count = 0;
 int minIndex = -1,mMaxIndex = -1;
 boolean target = false;
 for(int i=0;i<temp.length;i++){
 for(int j=i+1;j<temp.length;j++){
 char c = temp[i];
 char c1 = temp[j];
 if(c > c1){
 target = true;
 break;
 }
 }
 if(target){
 minIndex = i;
 break;
 }
 }
 target = false;
 for(int i= temp.length-1;i>=0;i--){
 for(int j=i-1;j>=0;j--){
 char c = temp[i];
 char c1 = temp[j];
 if(c < c1){
 target = true;
 break;
 }
 }
 if(target){
 mMaxIndex = i;
 break;
 }
 }
 count = minIndex==-1?0: mMaxIndex-minIndex+1;
 System.out.println("count:"+count);
 }

编辑于 2015-03-26 10:16:31 回复(0)

5雨6

 public static int getMinSortLength(int[] arr) {
 if(arr.length==0){
 return 0;
 }
 int max=arr[0];
 int min=arr[0];
 for(int i=1;i<arr.length;i++){
 if(max<arr[i]){
 max=arr[i];
 }
 if(min>arr[i]){
 min=arr[i];
 }
 }
 if(min!=arr[0]&&max!=arr[arr.length-1]){
 return arr.length;
 }else{
 if(min==arr[0]){
 int[] newarr=new int[arr.length-1];
 for(int i=1;i<arr.length;i++){
 newarr[i-1]=arr[i];
 }
 return getMinSortLength(newarr);
 }else{
 int[] newarr=new int[arr.length-1];
 for(int i=0;i<arr.length-1;i++){
 newarr[i]=arr[i];
 }
 return getMinSortLength(newarr);
 }
 }
 }

编辑于 2015-03-26 10:14:39 回复(0)

Captain

我这么觉得题目的意思这样就可以了

private static int sortArrayNum(long[] a){
 int rel =
  0;
 long[] temp = a.clone();
 Arrays.sort(temp);
 for(int i = 0 ; temp[i]<temp.length ; i++){
 if(a[i]!=temp[i]){
 rel++;
 }
 }
 return rel;
 }

编辑于 2015-03-26 10:15:42 回复(1)

Ghost

用冒泡或插入之类的排序算法对原数组进行排序，记录每个元素的移动距离，实际上问题就变成了求最长移动子串。

public class Solution {
 
 private byte[] recArr;

 public int getMinSortLength(int[] arr) { 
 int maxLength = 0;
 int recPoint = 0;
        
        if(arr.length == 0)
 return maxLength;
        
 recArr = new byte[arr.length];
 
 for(int i = 1;i < arr.length; ++i)
 for(int j = i;j > 0; --j)
 if(arr[j - 1] > arr[j]){
 recArr[i] = 1;
 recArr[j - 1] = 1;
 int temp = arr[j];
 arr[j] = arr[j - 1];
 arr[j - 1] = temp;
 }
 else
 break;
 
 maxLength = recArr[0];
 for(int i = 1;i < recArr.length; ++i){
 if(recArr[i] > 0)
 recArr[i] = (byte) (recArr[i] + recArr[i - 1]);
 if(recArr[i] > maxLength)
 maxLength = recArr[i];
 }

 return maxLength;
 }
}

发表于 2015-03-09 20:58:06 回复(0)

叶亚运

1. 先对给定的数组arr排序，为arrSort(升序);
2. 升序遍历无序数组arr, 如果arr[i]==arrSort[i],继续，否则返回i；
3. 降序遍历无序数组arr, 如果arr[i]==arrSort[i],继续，否则返回j；
4. 如果i=arr.length;或者j=0,返回0；否则返回结果j-i+1

public int getLen(int[]
  arr){
 //数组的复制
 int [] arrSort = Arrays.copyOf(arr,
  arr.length);
 Arrays.sort(arrSort);
 int i = getMin(int[]
  arr, int []arrSort);
 int j = getMax(int[] arr, int
  []arrSort);
 return j==0?0:(j-i+1);
 }
 private int
  getMin(int[] arr1, int[] arr2){
 int i;
 for(i = 0; i
  < arr1.length(); i ++){
 if(arr1[i] == arr2[i]){
 continue;
 }else{
 return i;
 }
 }
 return arr1.length();
 }
 private
  int getMax(int[] arr1, int[] arr2){
 int j;
 for(j =
  arr1.length(); j>=0; j--){
 if(arr1[j]==arr2[j]){
 continue;
 }else{
 return j;
 }
 }
 return 0;
 }

编辑于 2015-03-26 10:15:13 回复(0)

提交观点

问题信息

难度：

10条回答 7收藏 12411浏览

通过挑战的用户

迷茫的菜鸡只想搞钱

2023-02-24 13:12:06

求需要排序的最短子数组长度

问题信息

热门推荐

通过挑战的用户

相关试题