arrays - 给定未排序的数组，在线性时间和常数空间中找到 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 和 A[i] < A[j] 的索引。我已经通过O(n^2)使用 2 个 for 循环解决了它。

Answer 1

嗯...我会立即做出一个假设，如果这样i和j存在，那么也必须存在i和j这样的j == i + 1和A[i] < A[j]。如果是这样，该算法就变成了对数组的简单单次传递。

在你的第二个例子中，这将是i = 3and 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]情况。这里的所有都是它的。