查找排序数组中的所有差异
查找排序数组中的所有差异
提问于 2018-02-18 09:28:19
我有一个实值的排序(升序)数组，称它为(可能重复的)。我希望在给定值x，y的范围内，找到指数j存在的所有值(i)，以便: j>i和x <= aj-ai <= y，或者简单地说，查找在给定范围内存在“正向差异”的值。
输出是长度为a.Length的布尔数组。由于数组是排序的，所以x和y是正的。
我所做的最好的工作就是从每个索引开始，查看前面的子数组，对x+ai执行二进制搜索，并检查是否为aj<=y+ai。我想这是O(n log n)。有没有更好的方法？或者我能做些什么来加快速度。
我应该注意到，最终我想在同一个数组a上执行许多这样的范围x，y的搜索，但是范围的数目比数组的长度小得多(4-6个数量级)，因此我更关心搜索的复杂性。
示例：
a= 0, 1, 46, 100, 185, 216, 285对于范围x，y=99,101应该返回：
[true, true, false, false, true, false, false]只有值0、1和185在范围内存在正向差异。
内存中的代码可能有一些bug：
int bin_search_closesmaller(int arr[], int key, int low, int high)
{
if (low > high) return high;
int mid = (high - low)/2;
if (arr[mid] > key) return bin_search_closesmaller(arr, key, low, mid - 1);
if (arr[mid] < key) return bin_search_closesmaller(arr, key, mid + 1, high);
return mid;
}
bool[] findDiffs(int[] a, int x, int y)
{
bool[] result = new bool[a.Length];
for(int i=0; i<a.Length-1;i++)
{
int idx=bin_search_closesmaller(a, y+a[i], i+1, a.Length-1);
if (idx==-1) continue;
if (a[idx]-a[i] >= x) result[i]=true;
}
}谢谢!
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-02-18 10:07:48
只要对输入数组进行排序，问题就有一个线性的解决方案。关键是使用两个索引遍历数组a。
bool[] findDiffs(int[] a, int x, int y)
{
bool[] result = new boolean[a.Length];
int j = 0;
for (int i = 0; i < a.Length; ++i) {
while (j < a.Length && a[j] - a[i] < x) {
++j;
}
if (j < a.Length) {
result[i] = a[j] - a[i] <= y;
}
}
return result;
}使用a = [0,100,1000,1100]和(x,y) = (99,100)
i = 0, j = 0 => a[j] - a[i] = 0 < x=99 => ++j
i = 0, j = 1 => a[j] - a[i] = 100 <= y=100 => result[i] = true; ++i
i = 1, j = 1 => a[j] - a[i] = 0 < x=99 => ++j
i = 1, j = 2 => a[j] - a[i] = 900 > y=100 => result[i] = false; ++i
i = 2, j = 2 => a[j] - a[i] = 0 <= x=99 => ++j
i = 2, j = 3 => a[j] - a[i] = 100 <= y=100 => result[i] = true; ++i
i = 3, j = 3 => a[j] - a[i] = 0 <= x=99 => exit loopStack Overflow用户
发布于 2018-02-18 10:17:30
创建两个索引left和right并遍历数组。Right索引将一直移动到超出当前left 1的范围，然后检查前一个元素是否在范围内。索引只向前移动，因此算法是线性的。
right=2
for left = 0 to n-1:
while A[right] < A[left] + MaxRangeValue
right++
Result[left] = (A[right - 1] <= A[left] + MinRangeValue)关于这个算法的另一个观点是：
-while差太低，增量右
-while差太高，增量左
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48850179
复制相关文章
相似问题
腾讯云开发者
