在多次查询中，找到数组中第一个大于给定数字的元素的最有效方法是什么？

Question

我有一个数字数组。我的目标是找到第一个从起始索引向右移动时大于某个值k的元素的索引。

举个例子，如果数组是A = [4 3 3 4 6 7 1]，k = 3，起始索引是1（基于0的索引），那么大于k的第一个数的索引是3。 同样，如果k = 3并且起始索引为0，则第一个元素的索引为0。

预处理是可以的，因为我需要针对不同的k和起始索引处理多个查询。

[更新] 在任何“查找第一个索引”查询之间可能还会有一些数组更新查询。例如，索引=1的更新查询与值=2会将A更改为[4 5 3 4 6 7 1]

- user3243499

---

应该是3。已更新。谢谢。 - user3243499

你是否事先知道所有的查询？ - Pham Trung

在多个k值查询之间，还将进行一些数组值更新。 - user3243499

@PhamTrung 更新了描述。 - user3243499

你知道线段树吗？ - Pham Trung

Answer 1

如果您提前知道所有查询，那么有一个时间复杂度为 O(m log n) 的算法，其中 m 是查询数量，n 是元素数量。

从末尾向开头迭代数组，并维护一个双端队列结构。

- 在索引 i 处，我们尝试从队列的前面弹出所有小于当前值的元素。然后将索引 i 添加到队列中。我们可以轻松地看到队列中的所有值都是按升序排列的。 - 对于所有以索引 i 开始的查询，在队列中使用二分查找找到第一个大于 k 的元素。

伪代码：

Dequeue<Integer> q = new ArrayList<>();
for(int i = n - 1; i >= 0; i--){
    while(!q.isEmpty() && q.peek() <= data[i]){
         q.poll();
    }
    q.addFirst(i);
    for all query start at i {
         int st = 0;
         int ed = q.size();
         int re = -1;
         while(st <= ed){
             int mid = (st + ed)/2;
             if(data[q.get(mid)] > k){
                 re = q.get(mid); 
                 st = mid - 1;
             }else{
                 ed = mid + 1;
             }
         }
         print(re);
    }
}

由于数组可以实时更新，因此我们需要使用线段树来跟踪数组每个段中的最大元素。

- 对于每个查询，我们需要使用二分查找来搜索具有大于k的最大值的最小段。 - 时间复杂度为O(m log log n)，其中m是查询数量，n是元素数量。

伪代码：

Build segment tree from input array

for each query {
   if update query{
       update tree
   }else{
       int startIndex = starting index for this query;
       int start = startIndex;
       int end = ending index;
       int re = -1;
       while(start <= end){
           int mid = (start + end)/2;
           //Getting the maximum value in segment [startIndex, mid]
           if(tree.maximumInSegment(startIndex, mid) > k){
                 re = mid;
                 end = mid - 1; 
           }else{
                 start = mid + 1;
           }
       }
       print re;
   }
} 

- Pham Trung

Answer 2

线段树方法：给定值x和范围a[l…r]，找到范围a[l…r]内最小的i，使得a[i]大于x。

可以使用线段树上的最大前缀查询进行二分查找来解决此任务。然而，这将导致O(log^2(n))的解决方案。

通过沿着树向左或向右移动，取决于左子树的最大值，从而在O(logn)时间内找到答案的位置。

int get_first(int v, int lv, int rv, int l, int r, int x) {
if(lv > r || rv < l) return -1;
if(l <= lv && rv <= r) {
    if(t[v] <= x) return -1;
    while(lv != rv) {
        int mid = lv + (rv-lv)/2;
        if(t[2*v] > x) {
            v = 2*v;
            rv = mid;
        }else {
            v = 2*v+1;
            lv = mid+1;
        }
    }
    return lv;
}

int mid = lv + (rv-lv)/2;
int rs = get_first(2*v, lv, mid, l, r, x);
if(rs != -1) return rs;
return get_first(2*v+1, mid+1, rv, l ,r, x);

如需更多关于线段树的澄清，请查看以下内容：线段树

- Saksham Srivastav

Answer 3

根据数据和查询，可能更有效的方法是采用朴素的方法。前往起始索引，然后简单地查找大于k的值。

array = [4, 3, 3, 4, 6, 7, 1]
# eliminate candidates based on starting_index
candidate_set = [3, 3, 4, 6, 7, 1]
# find index of first element greater than k in linear time
result = 2 + starting_index

你应该先尝试这个。

---

如果您发现可以根据值（而不是基于起始索引）更快地缩小候选集，则也可以尝试该方法：

array = [4, 3, 3, 4, 6, 7, 1]

预处理步骤: 拥有一个索引，该索引按照排序后的值生成数组索引顺序。(如果您更新了数组，则现在还必须更新索引。)

# first column value, second column array index
index = [(1, 6), (3, 1), (3, 2), (4, 0), (4, 3), (6, 4), (7, 5)]

使用数组二分法或二分搜索，检索值大于k = 3的数组索引列表。

candidate_set = [(4, 0), (4, 3), (6, 4), (7, 5)]

过滤掉起始索引不大于1的候选项。

candidate_set = [(4, 3), (6, 4), (7, 5)]

通过遍历此列表选择最小的数组索引。

result = 3

---

如果您想花一些内存来节省后续的CPU周期，您可以添加记忆化甚至预先计算所有可能查询的结果并将其存储到查找表中。（并考虑缓存失效。）

- moooeeeep

---

你能否请再详细解释一下预处理步骤，最好能用一个简单的例子来说明。我还不是很清楚。 - user3243499

@user3243499 我已经添加了一些示例。 - moooeeeep

Answer 4

算法步骤。

1. 将数组值映射到索引，map.put(A[0],array[values])
2. 使用唯一值/数组值（例如数组A）的Set对键进行排序
3. 二分查找大于K的值的键
4. 将索引从map中获取为mapIndex[] = map.get(value > k)
5. 找到满足mapIndex[i] >= StartingIndex的索引

- venkatReddi