对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。
给定一个整数数组A及它的大小n，请返回最短子数组的长度。
测试样例：
[1,5,3,4,2,6,7],7
返回：4
[编程题]最短排序
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
// write code here
int k = -1;
int max = A[0];
for(int i=1;i<n;i++){
if(max > A[i])
k = i;
else
max = A[i];
}
if(k==-1)return 0;
int m = -1;
int min = A[n-1];
for(int i=n-2;i>=0;i--){
if(min < A[i])
m = i;
else
min = A[i];
}
return k-m+1;
}
};
编辑于 2015-10-06 23:47:41
回复(12)
python solution,时间复杂度为排序的时间复杂度NlogN。
思路，先把数组排序得到一个排序数组，针对两个数组（排序和未排序）同时进行遍历，如果第一次遇到了某个位置不相同，那么，这个位置一定是起始位置。如果是第二次甚至是第三次……，那么这个位置就做为结束位置，遍历完，将end-start+1就得到了结果。
class ShortSubsequence:
def findShortest(self, A, n):
B, start, end, canEnd = sorted(A), 0, -1, False
for i, v in enumerate(A):
if v != B[i]:
if not canEnd:
start = i
canEnd = True
else:
end = i
return end - start + 1
编辑于 2017-11-07 18:40:57
回复(5)
//两次遍历，题目中[1,5,3,4,2,6,7],7，我们要找到5和2的位置，怎么找呢？
他们2个有什么特征呢？他们都阻碍了单调性，而2是从左到右最后一个阻碍单调性的元素
而5是从右到左最后一个阻碍单调性的元素，知道之后我们需要两次遍历，一次从左到右，一次从右到左，具体怎么找看下面代码注释把！
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
// write code here
int max=A[0];
int min=A[n-1];
int m=-1;
int nn=-1;
for(int i=1;i<n;i++)
if(max<=A[i])//遍历的时候找最大值，如果某个数大于最大值，更新最大值
max=A[i];
else
m=i;//否则记录下他的位置，他可能就是最后一个元素影响到了单调性
for(int j=n-1;j>=0;j--)//同上
if(min>=A[j])
min=A[j];
else
nn=j;
if(m==-1)
return 0;
else
return m-nn+1;
}
};
发表于 2017-04-28 18:28:32
回复(0)
//测试数据{1,2,10,1,8,9} 结果是4//但是这个测试明明就是5才对啊，所以测试用例错了classShortSubsequence {public:intfindShortest(vector<int> A, intn) {// write code hereintlen=n;intmin=A[len-1];intminIndex=-1;for(inti=len-2;i>=0;i--){if(A[i]>min)minIndex=i;elsemin=A[i];}if(minIndex==-1)return0;intmax=A[0];intmaxIndex=-1;for(inti=1;i<len;i++){if(A[i]<max)maxIndex=i;elsemax=A[i];}returnmaxIndex-minIndex+1;}};
发表于 2015-09-25 16:01:37
回复(3)
import java.util.*;
public class ShortSubsequence {
public int findShortest(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(B);
int indexStart=0;
for(int i=0;i<n;i++){
if(A[i]!=B[i]){
indexStart=i;
break;
}
}
int indexEnd=0;
for(int j=n-1;j>=0;j--){
if(A[j]!=B[j]){
indexEnd=j+1;
break;
}
}
return (indexEnd-indexStart)>0?(indexEnd-indexStart):0;
}
}
发表于 2018-10-12 12:45:42
回复(0)
用了个骚操作，用两个指针一个在头一个在尾，先判断头指针与A[i+1:]的最小值比较，然后不断后移直到A[i] 比 A[i+1:]中最小的还要大就停止，然后尾指针开始移动不断用A[j] 与A[i:j]中的最大值比较。最后用j-i+1就是中间需要排序的大小
class ShortSubsequence: def findShortest(self, A, n): i, j = 0, n-1 while min(A[i + 1:]) >= A[i]: i += 1 if i >= n-1: return 0 while A[j] >= max(A[i:j]): j -= 1 return j-i+1
发表于 2018-08-15 21:00:48
回复(0)
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
// write code here
vector<int> B(A.begin(),A.end());
sort(B.begin(),B.end());
int i=0,j=A.size()-1;
for(;i<A.size();i++)
if(A[i]!=B[i])
break;
for(;j>=0;j--)
if(A[j]!=B[j])
break;
return -(j-i+1)==A.size()?0:(j-i+1);
}
};
发表于 2018-01-19 21:59:59
回复(0)
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
int k=-1,Max=A[0];
for(int i=1;i<n;i++)
{
if(Max > A[i])
k = i;
else
Max = A[i]; } if(k==-1) return 0; int m = -1; int Min = A[n-1]; for(int i=n-2;i>=0;i--) { if(Min < A[i]) m = i; else Min = A[i]; } return k-m+1;
}
};
发表于 2017-11-08 01:06:23
回复(0)
class ShortSubsequence {
public:
// Left 左边第一个不等的位置
// Right 右边第一个不等的位置
int findShortest(vector<int> A, int n) {
// write code here
int t[n],res = 0;
for(int i = 0; i < n; ++i) t[i] = A[i];
sort(A.begin(),A.end());
int Left = -1,Right = -1 ;
for(int i = n - 1; i >= 0; --i){
if(t[i] != A[i]){
Right = i;
break;
}
}
for(int i = 0; i < n;++i){
if(t[i] != A[i]){
Left = i;
break;
}
}
if(Left == Right && Left == -1) return 0;
else return Right - Left + 1;
}
};
发表于 2017-05-22 09:44:09
回复(1)
分两部分进行，第一步寻找起始地最小位置，第二部寻找最后的最大位置，两者相减便是最小子串的长度。 public class ShortSubsequence { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int A[] = { 1, 2, 10, 1, 8, 9 }; new ShortSubsequence().findShortest(A, 6); } public int findShortest(int[] A, int n) { // write code here int size = 1; int begin = 0; int end = n - 1; for (int i = 0; i < n - 1; i++) { int j = i + 1; for (; j < n; j++) { if (A[i] > A[j]) { break; } } if (j == n) { begin++; } else { break; } } for (int i = n - 1; i >= 1; i--) { int j = i - 1; for (; j >= 0; j--) { if (A[i] < A[j]) { break; } } if (j == -1) { end--; } else { break; } } System.out.println(end - begin + 1); if (end - begin + 1 < 0) return 0; return end - begin + 1; } }
发表于 2016-04-29 22:29:27
回复(0)
//我觉得是不是答案错了，答案的一个示例：{1,2,10,1,8,9} 结果是4
//我的代码运行结果是5，直观看来，答案就是5啊
import java.util.*;
public class ShortSubsequence {
public static void main(String[] args){
int[] A={1,5,3,4,2,6,7};
findShortest(A,A.length);
}
public static int findShortest(int[] A, int n) {
// write code here
int s=0;
while(s<n-1){
if(A[s+1]<A[s])
break;
else
s++;
}
if(s==(n-1))
return 0;
int min=A[s+1];
for(int j=n-1;j>s+1;j--){
if(A[j]<min){
min=A[j];
}
}
while(s>=0){
if(A[s]>min)
s--;
else
break;
}
int end=n-1;
while(end>s){
if(A[end-1]>A[end])
break;
else
end--;
}
int max=0;
for(int i=s+1;i<end;i++){
if(A[i]>max){
max=A[i];
}
}
while(end<n){
if(A[end]<max)
end++;
else
break;
}
return end-s-1;
} }
发表于 2015-09-09 16:37:02
回复(7)
思路：1.先判断依次最小值是否在正确位置，直到找到不在正确位置最小值的应该在的位置，作为最小需排序的起始点
2.依次判断最大值是否在正确位置，直到找不到正确位置最大值应该在的位置，作为最小需排序的末尾点
3.计算首末位点间的整数个数，即为需要排序的最短子数组长度
import java.util.*;
public class ShortSubsequence {
public int findShortest(int[] A, int n) {
int maxIndex = n-1;
int i=0;
for(;i<n;i++){
//判断当前子串最小值是否位置正确，若正确继续判断剩余子串最小值是否正确；
//若不正确，判断子串最大值位置是否正确
if(maxIndex==n-1){//
int tmp = findMin(A,i,n);
if(tmp==i){
continue;
}
}
int tmp = findMax(A,i,maxIndex+1);
if(maxIndex==tmp){//若子串最大值位置正确，更新子串最大值位置
maxIndex--;
i--;
continue;
}else{//若子串最大值位置不正确，结束循环
break;
}
}
return maxIndex-i+1;
} //寻找子串中的最小值的下标 public int findMin(int[] sub,int start, int n){
int min = sub[start];
int index = start;
for(int i=start+1;i<n;i++){
if(min>sub[i]){
min=sub[i];
index = i;
}
}
return index;
}
//寻找子串中的最大值的下标
public int findMax(int[] sub,int start, int n){
int max = sub[start];
int index = start;
for(int i=start+1;i<n;i++){
if(max<sub[i]){
max=sub[i];
index = i;
}
}
return index;
}
}
编辑于 2016-07-07 21:10:56
回复(0)
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
// write code here
int ans = 0;
vector<int>Max(n,0);
vector<int>Min(n,0);
// 每个元素左侧的最大值
for(int i=1;i<n;++i)
{
if(i==1) Max[i]= A[0];
else Max[i] = max(A[i-1],Max[i-1]);
}
// 每个元素右侧最小值
for(int i=n-2;i>=0;--i)
{
if(i==n-2) Min[i]=A[n-1];
else Min[i] = min(Min[i+1],A[i+1]);
}
int i = 0;
int j = n-1;
while(i<n && A[i]<=Min[i]) ++i;
while(j>=0 && A[j]>=Max[j]) --j;
if(i>=n || j<=0) return 0;
return j-i+1;
}
};
编辑于 2020-05-01 00:58:22
回复(0)
# -*- coding:utf-8 -*-
class ShortSubsequence:
def findShortest(self, A, n):
# write code here
list1=A
list1=sorted(list1)
re=[]
for i in range(n):
if list1[i]!=A[i]:
re.append(i)
if len(re)!=0:
return max(re)-min(re)+1
else:
return 0
找到与排好序的列表的不同的段，用最后的减去最前的位置加一就行了
编辑于 2019-07-22 20:35:21
回复(0)
//思路1：简单暴力，时间复杂度O(NlogN)+O(N)，空间复杂度O(N)
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
vector<int> B(A);//额外开辟一个数组复制A数组并且排序
sort(B.begin(),B.end());
int left=0,right=n-1;
while(left<=right && A[left]==B[left]) ++left;
while(left<=right && A[right]==B[right])--right;
//A从左到右不在最终位置的元素就是最短子数组长度
if(left>right) return 0;
return right-left+1;
}
};
//思路二：参考楼上大佬的代码，时间复杂度O(N) 空间复杂度O(1)
//根据样例模拟画个折线图会更好理解点
class ShortSubsequence {
public:
int findShortest(vector<int> A, int n) {
int right=0,max=A[0];
for(int i=1;i<n;++i)
if(A[i]>=max)
max=A[i];//若第i个数A[i]大于等于前面的最大值，说明从前面看过来不用排序
else
right=i;//否则,需要排序的子数组最右边界是i（i不断更新向右）
if(right==0) return 0;//right==0说明数组已经全局有序了
int left,min=A[n-1];//因为right不为0所以说明数组非全局有序，left一定会有值，所以不用赋初值
for(int i=n-1;i>=0;--i)
if(A[i]<=min)//同理，若第i个数A[i]小于等于后面的最小值，说明从后面看过来不用排序
min=A[i];
else
left=i;//否则，需要排序的子数组最是左边的边界是i（i不断更新向左）
return right-left+1;
}
};
编辑于 2019-03-16 15:49:19
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-09 17:55:26
-
2023-03-09 13:55:27
-
2023-03-09 07:38:16 -
2023-03-05 19:21:48
-
2023-02-21 22:16:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
