u***l
发帖数: 51 | 1 最优解时间复杂度是 O(n) 吗？
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
可能有重复值 | c******w
发帖数: 1108 | | t*****3
发帖数: 112 | 3 最差O(n)
【在 u***l 的大作中提到】
: 最优解时间复杂度是 O(n) 吗？
: Suppose a sorted array is rotated at some pivot unknown to you beforehand.
: (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
: 可能有重复值
| b******g
发帖数: 3616 | 4 最优解在最差情况下的时间复杂度是O(n)，对重复的数字不多的情况，则复杂度仍为O(
log n)
这题应该是不存在最差情况都能O(log n)的解的。举个例子，假设array的所有值是1，
一共n个1。要查找2，只有遍历所有元素才能判断2不在队列中。
【在 u***l 的大作中提到】
: 最优解时间复杂度是 O(n) 吗？
: Suppose a sorted array is rotated at some pivot unknown to you beforehand.
: (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
: 可能有重复值
|
|
