1

给定一个数字列表以及索引i和整数k ，我希望找到距离索引i处的数字最远（向左）且小于k的数字的索引。

eg
if the array is
Index :0 1 2 3 4 5 6 7 .....
Array :3 4 1 5 5 4 3 7 .....
Assuming i = 7 and k = 4 , the answer would be 0

我一直在尝试使用红黑树来实现这一点，但我不能低于 O(n) 。有什么方法可以通过使用不同的数据结构将复杂性降低到 O(logn) ？

4

2 回答 2

2

实际上，如果数组是静态的，并且您想为O(log n)每个数组进行多个查询，则不需要那种复杂的数据结构。

您实际要求的是-“距索引 i 处的数字最远（向左）且小于 k 的数字。” - 可以转换为“之前最左边的数字i小于k”。然后你可以看到如下：

  • 找到小于 K 的最左边的数字 - 说它在 position j;
  • 如果j < i,j是问题的答案
  • 否则，没有这样的数字 - position 之前的所有条目i都大于或等于k.

要回答第一个问题，您需要知道的是：对于 position i，位置上的最小数字是多少0..i- 我们称之为min(i)。请注意，这min是i- 如果 的单调递减函数min(5) = 10，min(6) = 15因为min(6)是 位置 上的最小数字0，6并且必然包括位置 上的最小数字0，5我们知道它是 10 min。构造 - 如果我们调用数组a，则：min(0) = a[0]和min(i) = minimum(min(i - 1), a[i])for i > 0。）

使用此信息，您可以对最左边的索引执行二进制搜索，i例如min(i) < k. 然后，通过 的构造min，我们知道位置从0到的所有数字i - 1都大于或等于k。所以i一定是这个问题的答案。

于 2012-10-10T22:38:28.507 回答
1

一种方法是构建一个数组mp，其中包含每 0 <= j < n 的前 j 个元素的最小值的索引：

int minPos = 0;
for (int i = 0; i < n; ++i) {
    if (a[i] < a[minPos]) minPos = i;
    mp[i] = minPos;
}

这显然需要 O(n) 时间。

中的元素mp将引用输入数组a中具有递减值的元素。给定一个查询 (i, k)，您现在可以mp在 [0, i - 1] 范围内对 k 进行二分搜索，使用间接方法从最小索引中获取实际最小值：

int find(int i, int k) {
    int start = 0;
    int end = i - 1;

    if (a[mp[end]] >= k) return -1;    // Not found.
    if (a[mp[start]] < k) return mp[start];    // The first element is smaller.

    // We maintain the invariant that a[mp[start]] is >= k and a[mp[end]] is < k.
    while (end - start > 1) {
        int mid = (start + end) / 2;
        if (a[mp[mid]] < k) {
            end = mid;
        } else {
            start = mid;
        }
    }

    return mp[end];
}
于 2012-10-10T22:43:24.180 回答