首页 > 试题广场 >

最小调整有序

[编程题]最小调整有序

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

给定一个int整数数组A及其大小n，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，即找出符合条件的最短序列。请返回一个二元组，元组的两个元素分别代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。要求A中元素均为正整数。

测试样例：

[1,4,6,5,9,10],6

返回：[2,3]

算法知识视频讲解

推荐

念润

大牛勿喷。。。。。

思路

进行两次遍历，一次从左到右找出N，一次从右到左找出M

（1）从左到右找出N

如果当前元素小于之前的最大元素则说明当前元素应处于[M N]无序序列中而且当前元素是当前最大下标的无序元素所以更新N为当前元素下标。

（2）从右到左找出M

如果当前元素大于之前的最小元素则说明当前元素应处于[M N]无序序列中而且当前元素是当前最小下标的无序元素所以更新M为当前元素下标

代码

class Rearrange {
public:
    vector<int> findSegment(vector<int> A, int n) {
        vector<int> result;
        int size = A.size();
        if(size == 0 || n <= 0){
            return result;
        }//if
        int M = 0,N = 0;
        int max = A[0];
        // 计算[M,N]中的N
        // 如果当前元素小于之前的最大元素则说明当前元素应处于[M N]无序序列中
        // 而且当前元素是当前最大下标的无序元素所以更新N为当前元素下标
        for(int i = 1;i < n;++i) {
            if (A[i] >= max){
                max = A[i];
            }//if
            else{
                N = i;
            }//else
        }//for
        int min = A[n-1];
        // 计算[M,N]中的M
        // 如果当前元素大于之前的最小元素则说明当前元素应处于[M N]无序序列中
        // 而且当前元素是当前最小下标的无序元素所以更新M为当前元素下标
        for(int i = n - 2;i >= 0;--i) {
            if(A[i] <= min){
                min = A[i];
            }//if
            else{
                M = i;
            }//else
        }//for
        result.push_back(M);
        result.push_back(N);
        return result;
    }
};

编辑于 2015-08-18 18:38:25 回复(16)

Java

Jlu小童

import java.util.*;
public class Rearrange {
    public int[] findSegment(int[] A, int n) {
        // write code here
        int[] ATemp=new int[n];
        System.arraycopy(A, 0, ATemp, 0, n);
        Arrays.sort(ATemp);
        int left=0;
        while(left < n){
            if(ATemp[left] != A[left])
                break;
            left++;
        }
        int right=n-1;
        while(right >= 0){
            if(ATemp[right] != A[right])
                break;
            right--;
        }
        if(left==n || right==0)
            return new int[2];
        else{
            int[] ret={left, right};
            return ret;
        }
    }
}

发表于 2022-01-05 15:15:15 回复(0)

Java

SnailLLL

import java.util.*;

public class Rearrange {
    public int[] findSegment(int[] A, int n) {
        // write code here
        int[] B=new int[n];
        for(int i=0;i<n;i++){
            B[i]=A[i];
        }
        Arrays.sort(A);
        int x=0;
        int y=n-1;
        boolean x_flag=false;
        boolean y_flag=false;
        while(x<y){
            if(B[x]!=A[x]){
                x_flag=true;
            }
            if(!x_flag){
                x++;
            }
            if(B[y]!=A[y]){
                y_flag=true;
            }
            if(!y_flag){
                y--;
            }
            if(x_flag && y_flag){
                break;
            }
        }
        if(x>=y) return new int[]{0,0};
        else return new int[]{x,y};
    }
}

发表于 2021-10-18 11:32:13 回复(0)