假設有一個長度為 n 的陣列，按照升序排序，並且進行了 1 到 n 次旋轉。
例如，陣列 nums = [0,1,2,4,5,6,7] 可能會變成：
[4,5,6,7,0,1,2] 如果旋轉了 4 次。
[0,1,2,4,5,6,7] 如果旋轉了 7 次。
注意，將陣列 [a[0], a[1], a[2], ..., a[n-1]]
旋轉 1 次會得到陣列 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
給定已排序且元素唯一的旋轉陣列 nums，請回傳該陣列中的最小元素。
你必須撰寫一個在 O(log n) 時間內運行的演算法。
解題思路
以二元搜尋樹的方式，找出最小值。
Code
Java:
Runtime 0 ms(100%), Memory 42.4 MB(29.4%)
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
|
class Solution {
public class ValueDuplicateException extends Exception {
public ValueDuplicateException(String message) {
super(message);
}
}
public int findMin(int[] nums) {
int leftFlag = 0;
int rightFlag = nums.length - 1;
while(leftFlag < rightFlag){
int midFlag = (leftFlag + rightFlag) / 2;
// if mid value is greater then right, means min value is in the right side
if (nums[midFlag] > nums[rightFlag]){
leftFlag = midFlag + 1;
}
// if mid value is less then right, means min value is in the left side
else if(nums[midFlag] < nums[rightFlag]){
rightFlag = midFlag;
}
// if mid value equals to right, means it can not happen.
// there is no duplicate value. Raise Exception.
else{
// throw new ValueDuplicateException("Value is duplicate");
}
}
return nums[leftFlag];
}
}
|
Python3:
Runtime 57 ms(17.66%), Memory 16.7 MB(10.13%)
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:
class ValueDuplicateException(Exception):
pass
def findMin(self, nums: List[int]) -> int:
# variant binary search
left_flag = 0
right_flag = len(nums) - 1
while left_flag < right_flag:
mid_flag = (left_flag + right_flag) // 2
# if mid value is greater then right, means min value is in the right side
if nums[mid_flag] > nums[right_flag]:
left_flag = mid_flag + 1
# if mid value is less then right, means min value is in the left side
elif nums[mid_flag] < nums[right_flag]:
right_flag = mid_flag
# if mid value equals to right, means it can not happen.
# there is no duplicate value. Raise Exception.
elif nums[mid_flag] == nums[right_flag]:
raise ValueDuplicateException
return nums[left_flag]
|
C#:
Runtime 92 ms(33.48%), Memory 38.9 MB(57.81%)
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
|
using System;
public class Solution {
public class ValueDuplicateException : Exception {
public ValueDuplicateException(string message) : base(message) {
}
}
public int FindMin(int[] nums) {
int leftFlag = 0;
int rightFlag = nums.Length - 1;
while (leftFlag < rightFlag) {
int midFlag = (leftFlag + rightFlag) / 2;
if (nums[midFlag] > nums[rightFlag]) {
leftFlag = midFlag + 1;
}
else if (nums[midFlag] < nums[rightFlag]) {
rightFlag = midFlag;
}
else {
throw new ValueDuplicateException("Value is duplicate");
}
}
return nums[leftFlag];
}
}
|
Golang:
Runtime 4 ms(56.99%), Memory 2.5 MB(98.74%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func findMin(nums []int) int {
leftFlag := 0
rightFlag := len(nums) - 1
for leftFlag < rightFlag {
midFlag := (leftFlag + rightFlag) / 2
if nums[midFlag] > nums[rightFlag] {
// if mid value is greater than right, means the minimum value is in the right side
leftFlag = midFlag + 1
} else if nums[midFlag] < nums[rightFlag] {
// if mid value is less than right, means the minimum value is in the left side
rightFlag = midFlag
} else if nums[midFlag] == nums[rightFlag] {
// if mid value equals right, it means it cannot happen.
// There is no duplicate value. Throw an exception.
}
}
return nums[leftFlag]
}
|
C++:
Runtime 5 ms(39.12%), Memory 10.1 MB(70.97%)
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 left_flag = 0;
int right_flag = nums.size() - 1;
while (left_flag < right_flag) {
int mid_flag = ( left_flag + right_flag ) / 2;
if (nums[mid_flag] > nums[right_flag]){
left_flag = mid_flag + 1;
}
else if (nums[mid_flag] < nums[right_flag]){
right_flag = mid_flag;
}
else{
// throw ValueDuplicateException;
}
}
return nums[left_flag];
}
};
|
C:
Runtime 3 ms(74.5%), Memory 5.9 MB(92.41%)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int findMin(int* nums, int numsSize){
int leftFlag = 0;
int rightFlag = numsSize - 1;
while (leftFlag < rightFlag) {
int midFlag = (leftFlag + rightFlag) / 2;
// if mid value is greater than right, means the minimum value is in the right side
if (nums[midFlag] > nums[rightFlag]) {
leftFlag = midFlag + 1;
}
// if mid value is less than right, means the minimum value is in the left side
else if (nums[midFlag] < nums[rightFlag]) {
rightFlag = midFlag;
}
// if mid value equals right, it means it cannot happen.
// There is no duplicate value. Throw an exception.
else if (nums[midFlag] == nums[rightFlag]) {
// throw ValueDuplicateException();
}
}
return nums[leftFlag];
}
|