154. Find Minimum in Rotated Sorted Array II

  • 36.5%

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/#/description

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order 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).

Find the minimum element.

The array may contain duplicates.


剑指offer 8, leetcode 153

方法一:

剑指offer解法,全面考虑问题,只有中间和两边三个值都相等时,才会出现无法判断情况,需要从头到尾遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(n==1) return nums[0];
int left=0, right=n-1;
int mid = left;
while(nums[left]>=nums[right]){
if(right-left==1){
mid = right;
break;
}
mid = left+(right-left)/2;
if(nums[left]==nums[mid] && nums[mid]==nums[right])
return helper(nums, left, right);
if(nums[left]<=nums[mid])
left = mid;
else if(nums[mid]<=nums[right])
right = mid;
}
return nums[mid];
}

int helper(vector<int> nums, int left, int right){
int res = nums[left];
for(int i=left+1; i<right+1; i++){
res = min(nums[i], res);
}
return res;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int findMin(vector<int>& nums) {
int left=0, right=nums.size()-1;
if(nums.size()==1) return nums[0];
while(nums[left]>=nums[right]){
if(right-left==1)
return nums[right];
int mid = left+(right-left)/2;
if(nums[left]==nums[mid] && nums[left]==nums[right])
return lineSearch(nums, left, right);
if(nums[left]>nums[mid]){
right = mid;
}else if(nums[left]<=nums[mid]){
left = mid + 1;
}
}
return nums[left];
}

int lineSearch(vector<int>& nums, int left, int right){
int pos = left;
for(int i=left+1; i<=right; i++){
if(nums[i]<nums[pos])
pos=i;
}
return nums[pos];
}
};

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int findMin(vector<int> &num) {
int lo = 0;
int hi = num.size() - 1;
int mid = 0;

while(lo < hi) {
mid = lo + (hi - lo) / 2;

if (num[mid] > num[hi]) {
lo = mid + 1;
}
else if (num[mid] < num[hi]) {
hi = mid;
}
else { // when num[mid] and num[hi] are same
hi--;
}
}
return num[lo];
}
};

When num[mid] == num[hi], we couldn’t sure the position of minimum in mid’s left or right, so just let upper bound reduce one.


https://discuss.leetcode.com/topic/5182/rough-sketch-of-proof-why-o-lg-n-is-impossible

Rough sketch of proof why O(lg N) is impossible

Refer to this image: array config

Big version here: http://postimg.org/image/asbbeo2c9/

There are generally 3 types of array config, assuming sorted from smallest to biggest. x-axis is the array index, y-axis is the element value.

For non-duplicate case, you may use num[mid] > num[end] to distinguish (1)&(2) from (3), and thus safely eliminate half of the array, at each iteration.

For dup case, it is not as straightforward (impossible?) to distinguish between (1), (2) and (3), and hence eliminate half of the array by doing O(1) comparison, at each iteration.


8ms, 20.55%, June.20th, 2016

https://leetcode.com/discuss/19746/my-pretty-simple-code-to-solve-it

My pretty simple code to solve it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int findMin(vector<int> &num) {
int lo = 0;
int hi = num.size() - 1;
int mid = 0;

while(lo < hi) {
mid = lo + (hi - lo) / 2;

if (num[mid] > num[hi]) {
lo = mid + 1;
}
else if (num[mid] < num[hi]) {
hi = mid;
}
else { // when num[mid] and num[hi] are same
hi--;
}
}
return num[lo];
}
};

When num[mid] == num[hi], we couldn’t sure the position of minimum in mid’s left or right, so just let upper bound reduce one.


https://discuss.leetcode.com/topic/4253/one-simple-and-clear-method-with-o-1-space-and-worst-o-n-time

One simple and clear method with O(1) space and worst O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int findMin(vector<int> &num) {
if(num.empty())
return 0;
int i=0,j=num.size()-1;
while(i<j)
{
int mid=(i+j)/2;
if(num[j]<num[mid]){
i=mid+1;
}
else if(num[mid]<num[j]){
j=mid;
}
else{//num[mid]==num[j]
if(num[i]==num[mid]){//linear complexity
i++;
j--;
}
else
j=mid;
}
}
return num[j];
}
};

https://discuss.leetcode.com/topic/4264/my-c-solution-24ms-is-there-any-better-solution

My C++ solution 24ms is there any better solution ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int findMin(vector<int> &num) {
int start = 0;
int end = num.size()-1;
int mid;
while(start<end){
if(num[start]<num[end])
break;
mid = start+(end-start)/2;
if(num[mid]>num[end]){
start = mid+1;
}
else if(num[mid]==num[end]){
start++;
end--;
}
else
end= mid;
}
return num[start];
}
};

https://discuss.leetcode.com/topic/19165/8ms-13-lines-c-solution

8ms 13-lines C++ Solution

This problem is more or less the same as Find Minimum in Rotated Sorted Array. And one key difference is as stated in the solution tag. That is, due to duplicates, we may not be able to throw one half sometimes. And in this case, we could just apply linear search and the time complexity will become O(n).

The idea to solve this problem is still to use invariants. We set l to be the left pointer and r to be the right pointer. Since duplicates exist, the invatiant is nums[l] >= nums[r] (if it does not hold, then nums[l] will simply be the minimum). We then begin binary search by comparing nums[l], nums[r] with nums[mid].

  1. If nums[l] = nums[r] = nums[mid], simply apply linear search within nums[l..r].
  2. If nums[mid] <= nums[r], then the mininum cannot appear right to mid, so set r = mid;
  3. If nums[mid] > nums[r], then mid is in the first larger half and r is in the second smaller half, so the minimum is to the right of mid: set l = mid + 1.

The code is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (nums[l] >= nums[r]) {
int mid = (l & r) + ((l ^ r) >> 1);
if (nums[l] == nums[r] && nums[mid] == nums[l])
return findMinLinear(nums, l, r);
if (nums[mid] <= nums[r]) r = mid;
else l = mid + 1;
}
return nums[l];
}
private:
int findMinLinear(vector<int>& nums, int l, int r) {
int minnum = nums[l];
for (int p = l + 1; p <= r; p++)
minnum = min(minnum, nums[p]);
return minnum;
}
};

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Python solution. Worst case O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def findMin(self, nums):
beg = 0
end = len(nums)-1
while beg <= end:
while beg < end and nums[beg] == nums[beg + 1]:
beg += 1
while end > beg and nums[end] == nums[end - 1]:
end -= 1
if beg == end:
return nums[beg]

mid = (beg+end)/2
if nums[mid] > nums[end]:
beg = mid + 1
else:
end = mid


return nums[beg]

Solution Mime:

64ms, 20.87%, June.20th, 2016

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
rtype = nums[0]
for i in xrange(len(nums)):
if nums[i] < rtype:
rtype = nums[i]
return rtype

Solution Mime:

52ms, 65.53%, June.20th, 2016

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
while(l < r):
if nums[l] < nums[r]:
return nums[l]
mid = (l + r) / 2
if nums[mid] > nums[r]:
l = mid + 1
elif nums[mid] < nums[r]:
r = mid
else:
l += 1
return nums[l]

1ms, 6.02%, June.20th, 2016

https://leetcode.com/discuss/60147/super-simple-and-clean-java-binary-search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length-1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < nums[r]) {
r = mid;
} else if (nums[mid] > nums[r]){
l = mid + 1;
} else {
r--; //nums[mid]=nums[r] no idea, but we can eliminate nums[r];
}
}
return nums[l];
}
}
谢谢你,可爱的朋友。