题目
https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
解法
暴力解法， 0(n)不符合要求
有序，要到0(logn)，考虑二分查找，排序数组的查找问题首先考虑使用 二分法 解决，其可将遍历法的 线性级别 时间复杂度降低至 对数级别 。
定下大概思路，
接着弄清楚算法流程:
- 入口，设置 i, j 指针分别指向
numbers 数组左右两端，m = (i + j) // 2为每次二分的中点
循环二分：
- 比较 number[m] > number[j]
- number[m] < number[j]
- 特殊 number[m] == number[j]
是否可以用 numbers[m] 和 numbers[i] 比较做代替？
解析： 不可以。因为做比较的目的是判断 mm 在哪个排序数组中。但在 numbers[m] > numbers[i]情况下，无法判断 m 在哪个排序数组中。
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
| class Solution {
public int minArray(int[] numbers) {
if (numbers == null || numbers.length ==0) {
return Integer.MIN_VALUE;
}
int len = numbers.length;
int i=0, j = len-1;
while(i<j) {
int m = i + (j-i)/2;
if (numbers[m] > numbers[j]) {
i = m+1;
}
if (numbers[m] < numbers[j]) {
j = m;
}
if (numbers[m] == numbers[j]) {
j--;
}
if (numbers[m] > numbers[j]) {
i = m+1;
} else if(numbers[m] < numbers[j]) {
j = m;
} else {
j--;
}
}
return numbers[i];
}
}
|
