给定未排序的数组,找到i,j,使得线性时间和常数空间中的i <j和A [i] <A [j]

Question

例1:

输入:5 4 3 2 1

输出:无

例2:

输入:5 4 3 2 6 1

输出:0,4(索引)

请建议一种算法来找到这样的索引i,j,即线性时间和恒定额外空间中的i <j和A [i] <A [j].我O(n^2)用2 for循环解决了它.

Answer 1

嗯......我会立刻做出,如果这样的假设i和j存在的话,那么还必须存在i,并j使得j == i + 1和A[i] < A[j].如果是这样,算法将转变为数组上的一个简单的单遍.

在你的第二个例子中,那将是i = 3和j = 4.

事实上,我们说,我们发现i,并j使得A[i] < A[j]和i + 1 < j.我们来看看吧A[i + 1].如果A[i + 1]大于A[i],那么只需设置j = i + 1,我们就完成了.否则,如果A[i + 1]小于或等于A[i],则只需设置i = i + 1并重复.这将始终引导我们j == i + 1满足A[i] < A[j]要求的一对.

换句话说,只需查看你的阵列寻找A[i] < A[i + 1]情况.这里的所有都是它的.