153. Find Minimum in Rotated Sorted Array

  • 39.1%

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

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.

You may assume no duplicate exists in the array.


剑指offer 8

方法一:

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(n==0) return -1;
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])
right = mid;
else
left = mid;
}
return nums[mid];
}
};

剑指offer解法,有两种情况,

  1. nums[left] < nums[right], 返回的结果就是nums[left]
  2. nums[left] > nums[right]相对复杂一些。对于数组里只有两个的话,只要返回第二个就好了。否则,针对两种中间情况进行讨论就好了。
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 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])
left = mid;
else if(nums[mid]<nums[right])
right = mid;
}
return nums[mid];
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.empty()) return 0;
int left=0, right=nums.size()-1;
while(nums[left]>nums[right]){
if(right-left==1)
return nums[right];
int mid = left+(right-left)/2;
if(nums[mid]<nums[right])
right = mid;
else
left = mid+1;
}
return nums[left];
}
};

方法二:

我的代码实现:

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 n = nums.size();
if(n==0) return -1;
if(n==1) return nums[0];
int left = 0, right = n-1;
int mid;
while(left<right){
if(nums[left]<=nums[right])
return nums[left];
mid = left + (right-left)/2;
// <= 是考虑了left == mid的情况
if(nums[left]<=nums[mid])
left = mid+1;
else
right = mid;
}
return nums[left];
}
};

针对start和end进行循环,多重讨论而已。如果nums{start] < nums[end],则一定是顺序的了。返回结果。否则根据中间节点,选择讨论。得到两种情况。思路清晰明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findMin(vector<int> &num) {
int start=0,end=num.size()-1;

while (start<end) {
if (num[start]<num[end])
return num[start];

int mid = (start+end)/2;

if (num[mid]>=num[start]) {
start = mid+1;
} else {
end = mid;
}
}

return num[start];
}

方法三:

看起来挺厉害的一种方法啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int findMin(vector<int> &num) {
int low = 0, high = num.size() - 1;
// loop invariant: 1. low < high
// 2. mid != high and thus A[mid] != A[high] (no duplicate exists)
// 3. minimum is between [low, high]
// The proof that the loop will exit: after each iteration either the 'high' decreases
// or the 'low' increases, so the interval [low, high] will always shrink.
while (low < high) {
auto mid = low + (high - low) / 2;
if (num[mid] < num[high])
// the mininum is in the left part
high = mid;
else if (num[mid] > num[high])
// the mininum is in the right part
low = mid + 1;
}

return num[low];
}
};

4ms, 21.69%, June.19th, 2016

https://leetcode.com/discuss/13389/compact-and-clean-c-solution

Compact and clean C++ solution

Classic binary search problem.

Looking at subarray with index [start,end]. We can find out that if the first member is less than the last member, there’s no rotation in the array. So we could directly return the first element in this subarray.

If the first element is larger than the last one, then we compute the element in the middle, and compare it with the first element. If value of the element in the middle is larger than the first element, we know the rotation is at the second half of this array. Else, it is in the first half in the array.

Welcome to put your comments and suggestions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findMin(vector<int> &num) {
int start=0,end=num.size()-1;

while (start<end) {
if (num[start]<num[end])
return num[start];

int mid = (start+end)/2;

if (num[mid]>=num[start]) {
start = mid+1;
} else {
end = mid;
}
}

return num[start];
}

Some corner cases will be discussed here


https://discuss.leetcode.com/topic/14768/4ms-simple-c-code-with-explanation

4ms simple C++ code with explanation

In this problem, we have only three cases.

Case 1. The leftmost value is less than the rightmost value in the list: This means that the list is not rotated.

e.g> [1 2 3 4 5 6 7 ]

Case 2. The value in the middle of the list is greater than the leftmost and rightmost values in the list.

e.g> [ 4 5 6 7 0 1 2 3 ]

Case 3. The value in the middle of the list is less than the leftmost and rightmost values in the list.

e.g> [ 5 6 7 0 1 2 3 4 ]

As you see in the examples above, if we have case 1, we just return the leftmost value in the list. If we have case 2, we just move to the right side of the list. If we have case 3 we need to move to the left side of the list.

Following is the code that implements the concept described above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while(left < right) {
if(nums[left] < nums[right])
return nums[left];

int mid = (left + right)/2;
if(nums[mid] > nums[right])
left = mid + 1;
else
right = mid;
}

return nums[left];
}

https://discuss.leetcode.com/topic/5044/simplest-and-fastest-c-solution-o-lg-n-you-can-t-beat-this

Simplest and fastest C++ solution O(lg N), you can’t beat this!

Binary search: basically eliminate the impossible elements by half each time by exploiting the sorted property.

1
2
3
4
5
6
7
8
9
int findMin(vector<int> &num) {
int lo =0, hi = num.size()-1;
while(lo<hi){
int mid=(lo+hi)/2;
if(num[mid]>num[hi]) lo=mid+1;
else hi=mid;
}
return num[lo];
}

https://discuss.leetcode.com/topic/6112/a-concise-solution-with-proof-in-the-comment

A concise solution with proof in the comment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int findMin(vector<int> &num) {
int low = 0, high = num.size() - 1;
// loop invariant: 1. low < high
// 2. mid != high and thus A[mid] != A[high] (no duplicate exists)
// 3. minimum is between [low, high]
// The proof that the loop will exit: after each iteration either the 'high' decreases
// or the 'low' increases, so the interval [low, high] will always shrink.
while (low < high) {
auto mid = low + (high - low) / 2;
if (num[mid] < num[high])
// the mininum is in the left part
high = mid;
else if (num[mid] > num[high])
// the mininum is in the right part
low = mid + 1;
}

return num[low];
}
};

https://discuss.leetcode.com/topic/26884/9-line-python-clean-code

9-line python clean code

Just use binary search

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

Solution Mine:

52ms, 50.58%, June.19th, 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)-1):
if nums[i] > nums[i+1]:
rtype = nums[i+1]
return rtype

Solution Mine:

64ms, 18.65%, June.19th, 2016

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

Solution 1:

56ms, 34.04%, June.19th, 2016

https://leetcode.com/discuss/63514/9-line-python-clean-code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
while(l < r):
mid = (l + r) / 2
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]
谢谢你,可爱的朋友。