-
Notifications
You must be signed in to change notification settings - Fork 149
Expand file tree
/
Copy pathMinNumber8.java
More file actions
99 lines (90 loc) · 2.38 KB
/
MinNumber8.java
File metadata and controls
99 lines (90 loc) · 2.38 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package com.so;
/**
* 第8题
* 输入一个非递减排序数组的一个旋转，输出旋转数组的最小元素。
*
* @author qgl
* @date 2017/08/09
*/
public class MinNumber8 {
/**
* 解法一：二分查找（寻找变化点）
* 时间复杂度：O(log n)，空间复杂度：O(1)
*
* @param array
* @return
*/
public static int minInReversingList(int[] array) {
if (array == null || array.length == 0) {
return -1;
}
if (array.length == 1 || array[array.length - 1] > array[0]) {
return array[0];
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > array[mid + 1]) {
return array[mid + 1];
}
if (array[mid - 1] > array[mid]) {
return array[mid];
}
if (array[mid] > array[0]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
/**
* 解法二：二分查找（最左下标）
* 时间复杂度：O(log n)，空间复杂度：O(1)
*
* @param nums
* @return
*/
public int minInReversingList2(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
/**
* 第8.1题：若非递减排序数组中有重复元素，求最小元素
* 时间复杂度：O(log n)，空间复杂度：O(1)
*
* @param nums
* @return
*/
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right--;
}
}
return nums[left];
}
}