我有一个解决方案。
您说数组可以是
1) 数字均匀分布在范围内
2) 有相当长的连续数字序列。
因此,首先我们开始进行简单的测试,以确保它是类型1还是类型2。
要测试类型1,
长度 = array.length;
范围 = array[length-1] - array[0];
现在考虑数组中的值
{length(1/5),length(2/5),length(3/5),length(4/5)},
如果数组分配是类型1,则我们近似知道array[i]必须是什么值,所以我们检查上述4个位置是否接近已知值,如果是等分布。
如果它们很接近,则为等分布,因此我们可以轻松找到数组中的任何元素。 如果我们无法根据上述方法找到元素,则认为它是类型2。
如果上述测试失败,则为类型2,这意味着在数组中存在少量连续数字序列的位置。
所以,我们可以用二分查找的方式来解决它。以下是解释:
*首先,在数组的中间位置进行搜索(例如在长度/2处,索引为i)
left=0,right=length;
BEGIN:
i=(left+right)/2;
情况a.1:我们要查找的数字大于数组[i]
left=i;
*现在我们检查该位置是否存在长连续序列,即array[i]、array[i+1]、array[i+2]是连续的整数。
情况a.1.1:(如果它们是连续的),
由于它们是连续的,并且序列可能很长,我们直接根据我们的搜索整数值在特定的索引处进行搜索。
例如,如果我们要搜索的整数是10,序列是5、6、7、8、9、10、11、15、100、103,而array[i]=5,则我们直接在array[i+10-5]处进行搜索,
如果我们找到了我们要搜索的整数,则返回它,否则只能从情况a.2继续[因为它显然会小于它],将right设置为
right=(array[i+10-5])
情况a.1.2,如果它们不连续
从BEGIN继续;
情况a.2:我们搜索的数字小于数组[i],
*情况a.2与a.1完全相似
*同样检查是否有后退序列,即array[i-2],array[i-1],array[i]按顺序排列,
如果它们按顺序排列,就像在情况a.1.1中一样向后搜索到精确值
如果它们不连续,请重复类似于情况a.1.2。
情况a.3,这是我们搜索的整数,
然后返回它。
希望这有所帮助
Map
中将会得到O(1)
的搜索时间,但设置需要O(n)
的时间。另外,你不需要实现二分查找,Arrays.binarySearch
已经可以满足你的要求。 - Boris the Spiderx[end] - x[start] == end - start
?),然后直接跳转到解决方案。请注意,此方法依赖于非常长的连续序列,否则您将无法消除许多递归阶段。 - Oliver Charlesworth