c++ - 查找输入数字以知道它应该在数组中的位置

Question

我有一个小算法问题。例如，我有一个数组。

array[10] = {23,54,10,63,52,36,41,7,20,22};

现在给定一个输入数字，例如 189，我想知道它应该位于哪个插槽中。例如，此输入应位于数组中的 4 个索引中，因为

23+54+10+63 = 150 and if we add 52 then sum will be 202 which will cover the range where 189 should lie. so the answer should be 4.

我想找到一个摊销的常数时间算法，可能在第一步中我们对数组进行一些预处理，以便我们可以在常数时间内获得所有下一个查询。

输入数字将始终介于 1 和数组中所有条目的总和之间
谢谢

score 1 · Accepted Answer

如果您确实需要恒定时间，请创建第二个数组，其大小是包含原始数组索引的最大总和值。所以 new_array[189] = 4;

score 0 · Accepted Answer

自然的解决方案是首先使用累积和构建一个数组。这看起来像

sums[10] = {23,77,87,...}

然后使用诸如lower_bound算法之类的二分查找来查找插入的位置。那将是O(log(n))。假设您的插槽数是恒定的，则此解决方案也是时间恒定的。但我猜你希望查找是O(1)根据插槽数。在这种情况下，您必须制作一个完整的查找表。由于这些数字的大小相对较小，这是完全可行的：

int lookup[N];
for(i=0,j=0;i<10;i++)
    for(k=0;k<sums[i];k++,j++)
        lookup[j]=i;

使用它，插槽号很简单lookup[number]。

score 0 · Accepted Answer

我认为你能得到的最好的方法是使用累积数组并通过使用二进制搜索以对数时间运行。我不确定是否存在具有恒定时间的解决方案。你确定有一个？

score 0 · Accepted Answer

如果您知道数字始终介于 1 和数组中所有项目的总和之间，那么平凡的常数时间算法是构建一个 [1..sum] 的数组，每个条目包含每个数字的正确槽。构建数组，你只需要做一次，是 O(N)。然后查找是 O(1)。

当然，这假设您有足够的内存用于数组。

除此之外，我认为你能做的最好的事情就是对总和使用二进制搜索 O(log(N)) 。

score 0 · Accepted Answer

假设

输入数字将始终介于 1 和数组中所有条目的总和之间

int total(0), i(0);
for(;total < inputValue; ++i)
{
    total += array[i];
}
//your answer is i-1

5 回答 5