标签: Binary Search

评分 0, 满分 5 星
0 票

For a random index m, compare nums[m] with its neighbor, one of the answer belongs to the interval that the bigger element belongs to too, and we can optimize our program based on this.

评分 0, 满分 5 星
0 票

首先O(n)预处理区间和,这样对每一段区间就可以进行O(1)的询问,很直观的一种方法是二分区间长度,总的时间复杂度是O(nlog(n))

评分 0, 满分 5 星
0 票

相比于前一个问题,这个题目允许出现重复数字,那么就不可以简单地根据mid位置的数字与当前已知的最小数字进行比较大小来划分答案所在的区间,主要指相等的情况。比如序列一:3 3 3 3 1 3,序列二:3 1 3 3 3 3。比较num[mid] = num[2]与num[r] = num[5],发现答案有可能在任意一区间,此时,两区间的最小就一定是答案了。用递归比较容易完成。

评分 0, 满分 5 星
0 票

这道题最初是Sure讲给我的,后来在LeetCode碰到了,好题。

方法一:借助插入排序的思想,复杂度O(m + n)。用两个指针分别指向两个数组的首地址(用两个代表数组下标的变量,不妨设idx_a,idx_b,初始为0),然后比较A[idx_a]和B[idx_b]的大小,值小的下标向后移动一个位置(idx_a++或idx_b++),然后继续比较,直到当前idx_a或者idx_b位置恰好处在两个数组的中间位置,记录下当前位置的值就是结果。至于m+n的奇偶情况对应处理就好。