我有一个实际值的排序(升序)数组,称之为a(可能重复).我希望在给定一系列值[x,y]的情况下,找到索引j所存在的值(i)的所有索引,以便：
j>我和
x< = a [j] -a [i]< = y
或者简单地说,找到在给定范围内存在“前向差异”的值.
j>我和
x< = a [j] -a [i]< = y
或者简单地说,找到在给定范围内存在“前向差异”的值.
输出是一个长度为a.Length的布尔数组.
由于数组对所有前向差异进行排序,因此x和y为正.
我设法做的最好的事情是从每个索引开始查看它前面的子阵列并执行二进制搜索x a [i]并检查是否[j]< = y a [i].我认为这是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]
仅对于值0,1和185在该范围内具有前向差异.
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,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;
}
}
谢谢！
解决方法
只要对输入数组进行排序,就可以找到问题的线性解决方案.关键是使用两个索引来遍历数组a.
bool[] findDiffs(int[] a,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,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 loop
