给定一个int整数数组A及其大小n,请编写一个函数,找出索引m和n,只要将m和n之间的元素排好序,整个数组就是有序的。注意:n-m应该越小越好,即找出符合条件的最短序列。请返回一个二元组,元组的两个元素分别代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序,返回[0,0])。要求A中元素均为正整数。
[1,4,6,5,9,10],6
返回:[2,3]
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; } };
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题