给定一个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) { // write code here vector<int> vec(A); sort(vec.begin(), vec.end()); int start = 0, end = 0; bool turn = false, first = true; for (int i = 0; i < A.size(); ++i) { if (A[i] != vec[i]) { start = i; break; } } for (int i = A.size() - 1; i >= 0; --i) { if (A[i] != vec[i]) { end = i; break; } } vector<int> result; result.push_back(start); result.push_back(end); return result; } };
import java.util.*; /* 思路:这题目说的不是很清楚,题目暗示的意思是不递减序列,我当时以为可能递增也可能递减,有点懵。 方法:用一个临时数组对原数组的内容排序,与原数组比较 第一个不相同的下标值和最后一个不相同的下标值就是起点和终点 那种找到两端无序值并且遍历判断中间是否有更小值得方法把我绕晕了。我最后没做出来,虽然我最开始是这样想的 */ public class Rearrange { public int[] findSegment(int[] A, int n) { int b[] ={0,0}; int c[]=new int[n]; if(n<=1) return b; for(int i=0;i<n;i++) c[i] =A[i]; Arrays.sort(c); int start =0; int end=n-1; while(c[start]==A[start]){ start++; if(start==n) return b; } while(c[end]==A[end]){ end--; if(end==0) return b; } b[0]=start; b[1]=end; return b; } } 运行时间:32ms 占用内存:8780k
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
//该题目,只针对升序序列的。如果为降序序列,反过来即可; vector<int> findSegment(vector<int> A, int n) { // write code here int len=A.size(); vector<int> vec; int left=0,right=0;//左边下界 if(n<=0) return vec; //第一次遍历,找到右界 int max=A[0]; for(int i=0;i<n;i++) { if(A[i]>=max) { max=A[i]; } else right=i; } //第二次从右向左,找到做界 int min=A[n-1]; for(int i=n-1;i>=0;i--) { if(A[i]<=min) min=A[i]; else left=i; } //从后面压入向量 vec.push_back(left); vec.push_back(right); return vec; }
class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { vector<int> res(2,0); if (n != A.size()) return res; vector<int> sortvt(A); sort(sortvt.begin(), sortvt.end()); int left = 0, right = n - 1; while (left <= n - 1) { if (sortvt[left] != A[left]) break; else ++left; } if (left == n) //A为有序数组 return res; while (right >= left) { if (sortvt[right] != A[right]) break; else --right; } res[0] = left; res[1] = right; return res; } };
class Rearrange { public: vector findSegment(vector A, int n) { // write code here vector<int> result; int start=n,end=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;++j) { if(A[j] < A[i]) { start = min(start,i); end = max(end,j); } } } if(start == n) start = 0; result.push_back(start); result.push_back(end); return result; } };
//最简单的行为动机表明,这题用冒泡排序 class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { // write code here int left,right; vector<int>res; right=0; left=n; bool flag=false; for(int i=0;i<n-1;++i){ for(int j=0;j<n-i-1;++j){ if(A[j]>A[j+1]){ left=min(left,j); right=max(right,j+1); swap(A[j],A[j+1]); flag=true; } } } if(flag){ res.push_back(left); res.push_back(right); return res; } else{ res.push_back(0); res.push_back(0); return res; } } };
class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { vector<int> v; int Max = A[0], Min = A[n-1],M=0,N=0; for(int i=1;i<n;i++){ if(A[i]>=Max) Max = A[i]; else M = i; } for(int i=n-2;i>=0;i--){ if(A[i]<=Min) Min = A[i]; else N = i; } v.push_back(N); v.push_back(M); return v; } };
import java.util.*; public class Rearrange { public int[] findSegment(int [] A,int n){ int b[] = {0,0}; int start = 0; int end =n-1; int max = A[0]; int min = A[n-1]; int m = 0; int l = 0; if(n<1){ return b; }else { for (int i=0;i<n;i++){ if(A[i]>=max){ max= A[i]; }else { m = i; } b[1] = m; } for (int i = n-2 ;i>0;i--){ if(A[i]<=min){ min = A[i]; }else { l = i; } } b[0] = l; } return b; } }
思路:分别从两头找,不满足顺序的坐标,设为x,y。然后找出x-y中的最大最小值,因为 这段序列很可能存在这个数组的最大最小值,所以然后分别从头和尾寻找比它们大的和小 的元素坐标,更新位置,最后的两个位置才是是答案。 class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { vector<int> res; int x=0; int y=0; int maxk=0; int mink=0; for(int i=0;i<n-1;i++) { if(A[i+1]<A[i]) { x=i;//从数组头部开始找出不满足递增顺序的第一个元素 break; } } for(int i=n-1;i>0;i--) { if(A[i]<A[i-1]) { y=i; //从数组尾部开始找出不满足递增顺序的第一个元素 break; } } mink=A[x]; maxk=A[x]; for(int i=x;i<=y;i++) { maxk=max(A[i],maxk); mink=min(A[i],mink);//找出这段序列中的最大,最小值 } for(int i=0;i<=x;i++)//更新位置坐标 { if(A[i]>mink) { x=i; break; } } int flag=0; for(int i=n-1;i>=y&&!flag;i--) { if(A[i]<maxk) { y=i; flag=1; } } res.push_back(x); res.push_back(y); return res; } };
public int[] findSegment(int[] A, int n) { int[] res = new int[2]; res[0] = 0; res[1] = n-1; boolean left=false,right=false; while (res[0] < res[1]){ for (int i=res[0]; i<=res[1]; i++){ if (A[i] < A[res[0]] && !left){//寻找左坐标,如果能找到了给它小的数,这就是结果 left = true; //找不到证明前面段有序 } if (A[i] > A[res[1]] && !right){//寻找右坐标,如果能找到了给它大的数,这就是结果 right = true; } if (left && right){ //均找到 return res; } } if (!left){ //左边还没没有找到 res[0]++; continue; } if (!right){//右边还没没有找到 res[1]--; continue; } } res[0] = 0; //有序 res[1] = 0; return res; }
先后检查升序和降序,复杂度为O(nlogn)。 class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { vector<int> res(2,0); vector<int> sorted = A; sort(sorted.begin(),sorted.end()); int i = 0,j = n - 1; while(i < n && A[i] == sorted[i]) ++i; while(j >= i && A[j] == sorted[j]) --j; if(i >= j) return vector<int>{0,0}; res[0] = i,res[1] = j; reverse(sorted.begin(),sorted.end()); i = 0,j = n - 1; while(i < n && A[i] == sorted[i]) ++i; while(j >= i && A[j] == sorted[j]) --j; if(i >= j) return vector<int>{0,0}; if(j - i < res[1] - res[0]) { res[0] = i,res[1] = j; } return res; } };
//两趟遍历 import java.util.*; public class Rearrange { public int[] findSegment(int[] A, int n) { // write code here int[] result = new int[2]; if(n <= 1) { return result; } int max = A[0]; for(int i = 1; i < n; i++) { if(A[i] < max) { result[1] = i; }else { max = A[i]; } } int min = A[n-1]; for(int i = n -2 ; i >= 0; i--) { if(A[i] > min) { result[0] = i; }else { min = A[i]; } } return result; } }
class Rearrange: def findSegment(self, A, n): l, r = 0, n - 1 while A[l] <= A[l + 1]: l += 1 if l == n - 1: return [0, 0] while A[r] >= A[r - 1]: #找到左右边界 r -= 1 r_ = A[l:r + 1] min_num, max_num = min(r_), max(r_) for i in range(l - 1, -2, -1): if i < 0 or A[i] <= min_num: l = i + 1 break for i in range(r + 1, n + 1): if i == n or A[i] >= max_num: r = i - 1 break return [l, r]
class Rearrange { public: vector<int> findSegment(vector<int> A, int n) { // write code here vector<int> temp = A; sort(temp.begin(), temp.end()); vector<int> result; for (int i = 0; i < A.size(); i++) { if (A[i] != temp[i]) { result.push_back(i); break; } } for (int i = A.size() - 1; i >= 0; i--) { if (A[i] != temp[i]) { result.push_back(i); } } if (result.empty()) { result.assign(2, 0); } return result; } };
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; } } }
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}; } }