首页 > 试题广场 >

最小调整有序

[编程题]最小调整有序
  • 热度指数: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)
class Rearrange:
    def findSegment(self, A, n):
        # write code here
        sort_A = sorted(A)
        res = []
        for i in range(n):
            if A[i] != sort_A[i]:
                res.append(i)
        return [res[0], res[-1]] if res else [0,0]
看和已经排序的有什么不一样
发表于 2018-08-22 19:22:24 回复(0)

python 2行解法:

思路,遍历数组,对于某个元素a,如果对应的值不等于排序数组的值,就把它的索引记录下来。最终返回[最小索引,最大索引]。

class Rearrange:
    def findSegment(self, A, n):
        res = filter(lambda c: A[c] != sorted(A)[c], range(n))
        return [min(res),max(res)] if res else [0, 0]
发表于 2017-11-15 20:55:00 回复(1)
思路一:对数组排序后比较第一个数不同和最后一个数不同,对应的索引就是m, n
时间复杂度为O(nlogn)
    def findSegment(self, A, n):
        sortedA = sorted(A)
        
        start = end = 0
        for i in range(n):
            if sortedA[i] != A[i] and start == 0:
                start = i
                break
        
        for i in range(n-1, -1, -1):
            if sortedA[i] != A[i] and end == 0:
                end = i
                break
        return start, end
思路二: 时间复杂度为O(n)
# -*- coding:utf-8 -*-

class Rearrange:
    def findSegment(self, A, n):
        if n < 2:
            return [0, 0]
        start = end = 0
        # 找到end, 从左到右遍历, 如果当前的最大值之后还有比最大值小的数,说明那个数就是end索引
        # 因为这个最大值应该与end位置的数交换
        # [1, 6, 5, 4, 3, 9, 10] 遍历到4,当前最大值为6,4 < 6,所以end 更新到 4的索引,
        # 再遍历到3, 当前最大值为6, 3 < 6, 所以end 更新到3的索引。
        # 求start 思路也是这样
        max = A[0]
        for i in range(n):
            if A[i] >= max:
                max = A[i]
            else:
                end = i
        # find the start
        min = A[n - 1]
        for i in range(n - 1, -1, -1):
            if A[i] <= min:
                min = A[i]
            else:
                start = i
        
        return start, end

编辑于 2016-08-10 09:47:49 回复(2)

问题信息

难度:
3条回答 18167浏览

热门推荐

通过挑战的用户

查看代码