给定一个int整数数组A及其大小n,请编写一个函数,找出索引m和n,只要将m和n之间的元素排好序,整个数组就是有序的。注意:n-m应该越小越好,即找出符合条件的最短序列。请返回一个二元组,元组的两个元素分别代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序,返回[0,0])。要求A中元素均为正整数。
测试样例:
[1,4,6,5,9,10],6
返回:[2,3]
给定一个int整数数组A及其大小n,请编写一个函数,找出索引m和n,只要将m和n之间的元素排好序,整个数组就是有序的。注意:n-m应该越小越好,即找出符合条件的最短序列。请返回一个二元组,元组的两个元素分别代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序,返回[0,0])。要求A中元素均为正整数。
[1,4,6,5,9,10],6
返回:[2,3]
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
# -*- 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