给定一个包含 n 个元素的数组。数组中的前 m 个元素已排序(没有重复)并且不为零。 数组的其余部分为零。
需要注意的是m是未知的 - 可以是任何东西,但众所周知 n >> m .
现在,给定 x;如果它存在于数组中,我应该返回它的索引,否则,它不存在。
现在的事情是我必须找到一个算法来做到这一点 .
一个简单的答案是只要下一个元素不为零就扫描数组,时间复杂度为 O(m),或者只是“二进制搜索”的修改版本,时间复杂度为 O(logn)。
除了这两个解决方案 - 我不知道。 已经暗示我们可以在 O(log m) 时间复杂度中找到 x,通过在 O(logm) 时间内找到 m 然后我可以对前 m 个元素进行二分搜索......但否则我不知道!
最佳答案
您可以找到 m
在 O(log m)
时间如下(考虑到第一个 m
元素不包含 0
)。
i = 1
while A[i] != 0 do
i = 2*i
return i
这为您提供了
m
的上限即最多 2m
(意思是 m <= i <= 2m
)。您所要做的就是对 i
进行二分查找。要查找的数组的第一个元素 x
.每个操作都可以在
O(log m)
中完成时间,所以总复杂度是 O(log m)
.
关于arrays - 如何在 m 排序数组中找到一个元素,其中数组的其余部分为零且未给出 m,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59736259/