在常数时间内找到排序数组中第一个大于给定 N 的整数

Question

假设我有一个整数排序数组

A

。

有没有 O(1) 的方法来获取大于给定整数的第一个元素的索引

n

？

在进行查询之前，我可以花费任意时间处理信息，但我不希望处理时间花费太长的时间。

约束条件为 1 ≤

n

、

|A|

、

A[i]

≤ 100

---

由于

A

的长度最多为 100，我当然可以构建另一个大小为 100 的数组，并为每个可能的

n

写出正确答案，但我想知道是否有一种更聪明的方法，不需要 O (n) 记忆。二分查找被丢弃，因为它不是 O(1)。

Answer 1

我将在应用程序开始时得到很多不同的排序数组。然后将进行数百万次查询，每个数组都应该返回正确的索引。

令

n

为列表中的最大长度数组，

M

为提供的数组数量，

arrays[i][j]

指数组

j

的位置

i

。这是一个算法，每次查询需要

O(n log(nM))

时间查找所有索引，空间复杂度为

O(nM)

，预处理时间为

O(nM log(nM))

。 （这比您

O(M)

所需的查询时间要快。）

预处理

1. 将所有数组项及其关联的数组索引存储在排序列表中。在Python中：

all_items = []
for i in range(M):
  for j in range(len(arrays[i])):
    all_items.append((arrays[i], i))
all_items.sort()

数组

all_items

包含每个数组的每个元素。这需要

O(nM log(nM))

时间。 （如果需要，可以通过进行排序数组合并来更有效地完成此操作。）

2. 预先计算

   all_items

   中每个元素的答案：也就是说，预先计算该项目在每个数组中的索引。这可以在

   O(nM)

   过程中完成：

curr_indexes = [0] * M
answers = []
for el, arr in all_items:
  answers.append(curr_indexes.copy())
  curr_indexes[arr] += 1
all_lengths = curr_indexes

查询

设

query_val

为查询值。

1. 二分查找

   all_items

   查找第一个值大于

   query_val

   的项目。这是

   O(log(nM))

   。调用该项目的索引

   query_idx

   。
2. 如果

   query_idx

   越界，则查询项大于每个数组中的每个元素：返回

   all_lengths

   。否则，返回

   answers[query_idx]

   。这是 O(1)。

该算法本质上提前回答每个可能值的查询，并尽可能高效地返回查询答案。