8-7例题2 leetcode719解题思路
来源：8-7 复杂的二分查找（2）
weixin_慕仙2234401
2022-02-05
老师好，对于leetcode719的二分查找解题有点疑惑
此题在解题时的left和right的定义是按照nums数组内元素的大小范围来决定的，所以这里的left, right和mid=(left+right)>>1感觉都是没有什么意义的？感觉是纯粹的猜一个数，然后再通过遍历的方式来判断这个mid能不能让我们满足k。如果分析时间复杂度的话这个方法应该是O(N^2)吗?
那为什么不使用“遍历然后求出数组元素之间的差值然后再排序”这个方法，这个方法的时间复杂度也是O(N^2)?
写回答
1回答
-
javaman
2022-02-12
同学， 你好。
(1) 二分的方法时间复杂度不是O(n ^ 2)。
这里时间复杂度是O(nlog(W))
这里的W是数组中最大值和最小值的差值 (全是非负数的话，W就是数组最大值), 按照题目给定的范围，可以取W = 1000000。 这里确实W和n是无关的，因为它是数值上的大小，而不是数组的规模。
判断是否是解的那部分是线性的O(n)，因为是i , j双指针，它们都一直增大不会减小，总共扫描元素的个数最多是2 * n。
所以二分本身逻辑O(low(W))，判断解复杂度O(n)，总题复杂度是O(n * log(W))
(2) "遍历然后求出数组元素之间的差值然后再排序"， 遍历差值已经O(n ^ 2)了，再排序，如果用朴素的O(n logn)的排序，复杂度为O(n ^ 2 logn)
00
相似问题