d********w
发帖数: 363 | 1 Given an array containing integers, you are required to find the indexes of
the smallest sub-array which on sorting will make the whole array sorted.
For e.g. 1 2 3 4 6 5 7 8 9 10
Output 4 5
Consider that such an array is somewhere in middle of the array. |
l*****a
发帖数: 14598 | 2 why not 5,6
of
sorted.
【在 d********w 的大作中提到】
: Given an array containing integers, you are required to find the indexes of
: the smallest sub-array which on sorting will make the whole array sorted.
: For e.g. 1 2 3 4 6 5 7 8 9 10
: Output 4 5
: Consider that such an array is somewhere in middle of the array.
|
S**I
发帖数: 15689 | 3 pair findSubArray(int A[], int size){
pair index(-1, -1);
int i = 0;
for(i = 0; i < size - 1; i++)
if(A[i] > A[i + 1])
break;
if(i == size - 1)
return index;
index.first = i;
for(i = size - 1; i > 0; i--){
if(A[i] < A[i - 1])
break;
index.second = i;
return index;
}
of
【在 d********w 的大作中提到】
: Given an array containing integers, you are required to find the indexes of
: the smallest sub-array which on sorting will make the whole array sorted.
: For e.g. 1 2 3 4 6 5 7 8 9 10
: Output 4 5
: Consider that such an array is somewhere in middle of the array.
|
r*******e
发帖数: 7583 | 4 这个明显不对，举例：
1 2 4 5 6 3 9 7 8
你的算法返回的是 6 3 9 7
能不能直接返回i，还跟这个sub-array的min和max有关
【在 S**I 的大作中提到】
: pair findSubArray(int A[], int size){
: pair index(-1, -1);
: int i = 0;
: for(i = 0; i < size - 1; i++)
: if(A[i] > A[i + 1])
: break;
: if(i == size - 1)
: return index;
: index.first = i;
: for(i = size - 1; i > 0; i--){
|
r*******e
发帖数: 7583 | 5 按这个算法找到first和last之后
还必须找出中间的min和max
然后first往前退直到 A[first] < min
last往后退直到 A[last] > max
【在 l*****a 的大作中提到】
: why not 5,6
:
: of
: sorted.
|
S**I
发帖数: 15689 | 6 LZ说假定这个subarray在中间；没这个假设的话当然要另当别论。
【在 r*******e 的大作中提到】
: 这个明显不对，举例：
: 1 2 4 5 6 3 9 7 8
: 你的算法返回的是 6 3 9 7
: 能不能直接返回i，还跟这个sub-array的min和max有关
|
v*******7
发帖数: 187 | 7
I agree with you, and still cost O(N) time complexity.
【在 r*******e 的大作中提到】
: 按这个算法找到first和last之后
: 还必须找出中间的min和max
: 然后first往前退直到 A[first] < min
: last往后退直到 A[last] > max
|
s*********l
发帖数: 103 | 8
of
#include
using namespace std;
template
pair unsorted_subarray(const vector &a)
{
T max_record, min_record;
int n = a.size();
assert(n>0);
vector max_record_ind, min_record_ind;
max_record = a[0]; max_record_ind.push_back(0);
min_record = a[n-1]; min_record_ind.push_back(n-1);
for (int i=1;i
if (a[i]>=max_record){
max_record = a[i]; max_record_ind.push_back(i);
}
}
for(int i=n-2;i>=0;i--){
if (a[i]<=min_record){
min_record = a[i]; min_record_ind.push_back(i);
}
}
int s1 = max_record_ind.size();
int s2 = min_record_ind.size();
int i=0;
while(max_record_ind[i]==min_record_ind[s2-i-1]) ++i;
if (i==max_record_ind.size()) return pair(-1,-1);
int j=0;
while(min_record_ind[j]==max_record_ind[s1-j-1]) ++j;
if (j==min_record_ind.size()) return pair(-1,-1);
return pair(max_record_ind[i],min_record_ind[j]);
}
【在 d********w 的大作中提到】
: Given an array containing integers, you are required to find the indexes of
: the smallest sub-array which on sorting will make the whole array sorted.
: For e.g. 1 2 3 4 6 5 7 8 9 10
: Output 4 5
: Consider that such an array is somewhere in middle of the array.
|
