对于一个无序数组A,请设计一个算法,求出需要排序的最短子数组的长度。
给定一个整数数组A及它的大小n,请返回最短子数组的长度。
测试样例:
[1,5,3,4,2,6,7],7
返回:4
int findShortest(vector<int> A, int n){
int pivot = A[0];
int RightPos = -1;
for (int i = 1; i < n; i++)
{
if (A[i] < pivot)
{
RightPos = i;
}
else
{
pivot = A[i];
}
}
pivot = A[n - 1];
int LeftPos = n;
for (int i = n - 2; i >= 0; i--)
{
if (A[i] > pivot)
{
LeftPos = i;
}
else
{
pivot = A[i];
}
}
return (LeftPos < RightPos) ? (RightPos - LeftPos + 1) : 0;
}