高效算法:给定一个未排序的正整数数组和一个整数N,如果N存在于数组中,则返回N或第一个数字<N

Question

我有这个问题:

给定未排序的正整数数组和整数N,如果数组中存在N,则返回N,或者小于N的第一个数字.

在一次采访中想知道解决它的最有效算法是什么？

我使用散列和排序数组给出了两种方法,但这不是正确有效的方法.如果有人能为这个问题提供最佳算法,我将非常感激.

Answer 1

我假设这是一种C风格的语言; 如果没有,请更新问题以反映语言.

如果数组没有排序,那么你别无选择,只能寻找一个(可能)完全遍历的数组N,因为任何排序操作都需要比简单遍历数组更长的时间(除了通过"盲目查找元素")运气").类似于此的东西可能是最有效的(除非我遗漏了一些东西)

int retVal = -1;

for(int i = 0; i < ARRAY_LENGTH; i++)
{
    if(array[i] == N) return N;
    if(retVal == -1 && array[i] < N) retVal = array[i];
}

return retVal;

正如其他地方所建议的,你可以修改

if(retVal == -1 && array[i] < N) retVal = array[i];

至

if(retVal < array[i] && array[i] < N) retVal = array[i];

为了获得小于的最大值N,而不是简单的第一个.

Answer 2

从头到尾扫描列表,如果您看到小于N的值,请抓住第一个,直到结束,或找到N.如果找到N,则返回,如果到达结尾,则返回你坚持的价值.据推测,如果所有值都大于N,则必须返回一些值,但问题并未说明.

O(N)性能,O(1)空间使用.

如果你正在寻找小于N的最大值,那就有点棘手了.在这种情况下,你不必保持小于N的第一个值,而是每次找到小于N的值时,只需抓取一个新值,但是大于您当前持有的值.

只需更换

if(array[i] < N && retVal == -1) retVal = array[i];

同

if(array[i] < N && retVal < array[i]) retVal = array[i];

在亚当的回答中