以下为ChatGPT自动生成的解答,正确与否请自行判断。 也许你也可以从大家的发帖中找到想要的答案!
BFE.devAI解答 - JavaScript 代码题
50. 含有重复元素的数组中返回特定元素之前的元素
可以通过二分查找的方法解决这个问题。具体步骤如下:
- 初始化左指针
left
为 0,右指针right
为数组长度减 1。 - 不断进行二分查找,直到找到第一个等于特定元素的位置,如果数组中不存在特定元素,则返回
undefined
。在查找过程中需要保证找到的下标不会越界。
代码实现如下:
function findElementBefore(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] === target) { if (mid - 1 >= 0) { return arr.slice(0, mid); } else { return undefined; } } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return undefined;}
这个函数的时间复杂度为 $O(\log n)$,空间复杂度为 $O(1)$。其中 slice
方法创建了一个新数组,空间复杂度可以优化,不过这里为了代码的可读性,暂时不做优化。