有没有什么好的算法实现可以从特定数组元素中找到最接近的负元素？

Question

我目前正在从事C编程，并且当当前索引定义为int变量idx时，我需要从数组中的idx中找到[0，idx-1]范围内最接近的负元素。

例如，如果array为1 -2 3 -4 5 6并且idx为5（array [idx]将为6），则函数必须返回3，因为< [-4是数组[idx]中最接近的负元素。

我知道如何线性地解决这个问题，例如

for(int i = idx-1; i>=0; i--){
   if(array[i] < 0) return i;
}

但是我想知道更快的算法（这意味着该算法具有较低的时间复杂度），因为我目前正在处理元素数超过百万的大型数组。有人可以帮忙吗？    

Answer 1

您可以创建一个位数组

一次为每个包含负数的索引设置一位。如果将此位数组存储为64位无符号整数，则可以同时检查64个索引。

如果您有1亿个条目，而每10,000个条目中只有一个为负，则可以创建第二个位数组，为第一个数组中的每个64位数字设置一个位。因此，检查该数组中的

one

数组元素可让您同时检查4096个条目。 当然还有更多代码。当负数很少时，速度更快。

如果必须在遍历数组时执行此操作，则这将变得更加容易。只记得最后的结果。假设您发现最接近索引500,000的负数位于索引493,005。现在，您希望最接近索引500,001的负数。可能在哪里？它可能位于索引500,000，并且如果该数字不是负数，那么它将再次位于＃493,005。对于所有i而言，在O（n）中进行计算很简单，而不是O（n ^ 2）。

Answer 2

O（N）是最好的方法，不需要其他信息。考虑一个不包含负值的数组。确定的唯一方法是访问整个数组。

Answer 3

如果数组很大，并且负数稀疏，则可以通过对8或16个数字的块进行或运算并将结果与​​0比较，来更快地执行。正或零的结果表示这些数字均不为负，负数的结果表示这些数字均为至少一个，您可以通过更简单的循环（无边界条件）来找到它们。]

此方法产生的测试较少，并且数组元素的OR-ing块可以编译为矢量化代码，因此性能应该更好，但是复杂度保持不变：线性时间。仔细的基准测试将告诉您，根据您的数据集，这是否值得。