在范围内查找元素的高效查询
Efficient query for finding an element in a range
我遇到一个问题,我需要找到一个特定的成对总和,其中索引中的第一个元素的索引 > i
。
示例:
[1, 2, 3, 4, 6]
(索引 0
到 4
)
target_sum = 9
现在,我需要从这个数组中找到一个成对求和,其中索引中的第一个元素的索引 > i
。
现在,显而易见的解决方案是:
- 计算成对总和数组。
[1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6]
[ O(n^2) ]
- 遍历索引
i+1
到 n
以找到 target_sum。 [ O(n^2) ] (n为原数组的长度)
现在,主要问题是2。即使我无法改进(1),我也需要改进(2),因为这个会被很多人质疑。
我想到的一种方法:
- 从成对求和数组中创建索引、值对数组。 O(n^2) [n为原长度]
- 先按值排序数组,再按索引排序。 O(n^2 * logn)
- 对于每个查询,运行 二进制搜索以查找值存在的区间。 O(logn)
- 运行 对该区间的另一个二进制搜索以查找索引 >
i
.
有什么优雅更好的方法吗?
在 O(n^2)
中创建地图 sum -> highest first element index
。然后通过在映射中查找目标总和并确定 highest first element index
是否高于 i
.
来回答 O(1)
中的每个查询
我遇到一个问题,我需要找到一个特定的成对总和,其中索引中的第一个元素的索引 > i
。
示例:
[1, 2, 3, 4, 6]
(索引 0
到 4
)
target_sum = 9
现在,我需要从这个数组中找到一个成对求和,其中索引中的第一个元素的索引 > i
。
现在,显而易见的解决方案是:
- 计算成对总和数组。
[1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6]
[ O(n^2) ] - 遍历索引
i+1
到n
以找到 target_sum。 [ O(n^2) ] (n为原数组的长度)
现在,主要问题是2。即使我无法改进(1),我也需要改进(2),因为这个会被很多人质疑。
我想到的一种方法:
- 从成对求和数组中创建索引、值对数组。 O(n^2) [n为原长度]
- 先按值排序数组,再按索引排序。 O(n^2 * logn)
- 对于每个查询,运行 二进制搜索以查找值存在的区间。 O(logn)
- 运行 对该区间的另一个二进制搜索以查找索引 >
i
.
有什么优雅更好的方法吗?
在 O(n^2)
中创建地图 sum -> highest first element index
。然后通过在映射中查找目标总和并确定 highest first element index
是否高于 i
.
O(1)
中的每个查询