s******t
发帖数: 6 | 1 给一个int[] data，数组大小最大100K
实现 int[] findIndices(long low, long upper)，返回值从小到大排序，同一个data
，findIndices会被执行多次
例：[100, 300, 25, 123, 3, 157, 9, 103, 304], findIndices(100, 200) 返回 [0,
3, 5, 7]
我想到就两种方法：
1：loop数组一个一个比较
2：排序成 [ {3, 4}, {9, 6}, {25, 2}, {100, 0}, {103, 7}, {123, 3}, {157, 5},
{300, 1}, {304, 8} ]，然后binary search low and upper，得到index的数组，再
排序这个结果，返回。如上面的列子，先得到 [{100, 0}, {103, 7}, {123, 3}, {157
, 5}]，拿indces，[0, 7, 3, 5]，再sort得到[0, 3, 5, 7]
2在极端的情况下会更慢，因为结果要再排序。
请教有没有更快的方法？ | w*******o
发帖数: 113 | 2 你这个例子返回值也没从大到小排序啊。
私以为，挨个比较是最简单最快的方法。
for (int i = 0; i < len; i++) if (lower < nums[i] < upper) res.add(i); | s******t
发帖数: 6 | 3 不好意思，是小到大，已修改。
【在 w*******o 的大作中提到】
: 你这个例子返回值也没从大到小排序啊。
: 私以为，挨个比较是最简单最快的方法。
: for (int i = 0; i < len; i++) if (lower < nums[i] < upper) res.add(i);
| s******t
发帖数: 6 | | z*********n
发帖数: 1451 | 5 这是面试题吗？还是实际工程问题？
单纯追求更高速度，只能牺牲空间。
基于这个前提：“同一个data，findIndices会被执行多次”
最简单暴力的办法：
提前预处理计算好所有两两组合的结果，你的例子里，
预处理完后，应该有一项长成这样：
[100, 157] - [0,3,5,7]
至于输入的（100, 200）怎么map到[100,157],这个trivial吧。
这样的话预处理大概是n^3logn的时间，查询是logn的。
上面做法空间大小是 unique(A)^2*n (~=O(n^3))，按lz的数据规模，大了点
那就只能考虑牺牲查询时间，节约空间和欲处理时间：
考虑建个segment tree吧（按你的例子）：
[100, 300, 25, 123, 3, 157, 9, 103, 304]
排序后：
[3, 9, 25, 100, 103, 123, 157, 300, 304]
把上面这个数组建成segment tree，每个节点存对应range的坐标集合
类似：
（3...304)
[0,1,2,...,8]
/ \
(3...103) (123 ... 304)
[0, 2, 4, 6, 7] [1, 3, 5, 8]
/ \ / \
(3...25) (100...103) (123..157)(300..304)
....
这样查询100 200, 你直接在树里搜上下限，会取出来如下区间:
(100...103),(123..157),因为每个区间所携带的index集合已经是有序的，只要按集合
size从小到大merge，这样merge过程的复杂度渐近应该是O(n)的
总体预处理时间：nlogn, 查询时间lgn + n, 空间nlogn.
如果是面试，你自己的两个方案加上面的两个方案思考过程答一遍，即使它不是最优解
应该也能过了。
如果是工程，请用2楼的方案,直接扫一遍完事。
或者用我的方案1,找个分布式data pipeline引擎跑。 |
|
