11.旋转数组的最小数字
题目
牛客网
思路
方法：二分法
旋转数组将原本有序的数组分成了两部分有序的数组，因为在原始有序数组中，最小的元素一定是在首位，旋转后无序的点就是最小的数字。我们可以将旋转前的前半段命名为A，旋转后的前半段命名为B，旋转数组即将AB变成了BA，我们想知道最小的元素到底在哪里。
因为A部分和B部分都是各自有序的，所以我们还是想用分治来试试，每次比较中间值，确认目标值（最小元素）所在的区间。
复杂度分析：
- 时间复杂度：O(log2n)，二分法最坏情况对n取2的对数
- 空间复杂度：O(1)，常数级变量，无额外辅助空间
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
| public class Solution {
public int minNumberInRotateArray(int [] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (array[mid] > array[right]) {
left = mid + 1;
}
else if (array[mid] == array[right]) {
right--;
}
else {
right = mid;
}
}
return array[left];
}
}
|
53.数字在排序数组中出现的次数
题目
牛客网
思路
方法：二分法
因为data是一个非降序数组，它是有序的，这种时候我们可能会想到用二分查找。但是一个数组可能有多个k，而且我们要查找的并非常规二分法中k出现的位置，而是k出现的左界和k出现的右界。要是能刚好找到恰好小于k的数字位置和恰好大于k的数字的位置就好了。
再有因为数组中全是整数，因此我们可以考虑，用二分查找找到k+0.5应该出现的位置和k−0.5应该出现的位置，二者相减就是k出现的次数。
复杂度分析：
- 时间复杂度：O(log2n)，其中n为数组长度，两次二分查找，二分查找复杂度为O(log2n)
- 空间复杂度：O(1)，常数级变量，无额外辅助空间
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
| public class Solution {
public int binarySearch(int[] array, double k) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] < k) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left;
}
public int GetNumberOfK(int [] array , int k) {
return binarySearch(array, k + 0.5) - binarySearch(array, k - 0.5);
}
}
|
