给定一个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;
}
};
发表于 2016-04-19 21:48:51
回复(1)
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
发表于 2017-07-06 10:50:42
回复(2)
思路一：对数组排序后比较第一个数不同和最后一个数不同，对应的索引就是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)
//该题目，只针对升序序列的。如果为降序序列，反过来即可；
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;
}
发表于 2016-08-19 09:21:47
回复(0)
寻找最小和最大边界，申请了临时空间。
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; } };
编辑于 2015-09-04 14:45:32
回复(0)
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;
}
};
编辑于 2020-07-21 22:46:01
回复(0)
//最简单的行为动机表明，这题用冒泡排序
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;
}
}
};
发表于 2019-09-04 17:58:38
回复(0)
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;
}
};
发表于 2019-03-10 01:25:18
回复(0)
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;
}
}
发表于 2017-12-26 13:55:09
回复(0)
思路：分别从两头找，不满足顺序的坐标，设为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;
}
};
编辑于 2017-09-28 23:43:50
回复(0)
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;
}
发表于 2017-08-25 16:46:08
回复(0)
先后检查升序和降序，复杂度为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;
}
};
发表于 2017-07-01 11:07:04
回复(0)
//两趟遍历
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;
}
}
发表于 2017-06-09 20:44:37
回复(0)
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]
发表于 2017-03-08 23:06:12
回复(0)
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;
}
};
发表于 2016-08-31 16:23:07
回复(0)
class Rearrange {
public:
vector<int> findSegment(vector<int> A, int n)
{
int max_index=0,max_value=INT_MIN;
for(int i=0;i<A.size();i++)
{
if(max_value<=A[i])
{
max_value=A[i];
}
else
{
max_index=i;
}
}
int min_index=0,min_value=INT_MAX;
for(int i=A.size()-1;i>=0;i--)
{
if(min_value>=A[i])
{
min_value=A[i];
}
else
{
min_index=i;
}
}
vector<int>res;
res.push_back(min_index);
res.push_back(max_index);
return res;
}
};
public:
vector<int> findSegment(vector<int> A, int n)
{
int max_index=0,max_value=INT_MIN;
for(int i=0;i<A.size();i++)
{
if(max_value<=A[i])
{
max_value=A[i];
}
else
{
max_index=i;
}
}
int min_index=0,min_value=INT_MAX;
for(int i=A.size()-1;i>=0;i--)
{
if(min_value>=A[i])
{
min_value=A[i];
}
else
{
min_index=i;
}
}
vector<int>res;
res.push_back(min_index);
res.push_back(max_index);
return res;
}
};
发表于 2022-03-26 15:39:23
回复(0)
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)
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)
问题信息
难度：
58条回答
65收藏
19545浏览
通过挑战的用户
查看代码-
2022-12-07 20:36:05
-
2022-08-21 10:50:25
-
2022-08-20 08:19:35 -
2022-07-25 17:02:33
-
2022-06-24 19:06:20
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
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; } };