文章目录
其他题型见：剑指 offer 全记录之二分查找
287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
https://leetcode-cn.com/problems/find-the-duplicate-number/
class Solution {
public int findDuplicate(int[] nums) {
if (nums == null) {
return -1;
}
int len = nums.length;
if (len <= 0) {
return -1;
}
int left = 0, right = len - 1;
int res = -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
int count = 0;
for (int i = 0; i < len; i++) {
if (nums[i] <= mid) {
count++;
}
}
// 与 mid 比较，这里的二分 分的是数组的下标，所以可以使用二分
if (count <= mid) {
left = mid + 1;
} else {
right = mid - 1;
// 直接记录 mid 就可以了
res = mid;
}
}
return res;
}
}
- 时间：O(n*logN)
- 空间：O(1)
剑指 Offer 11. 旋转数组的最小数字
class Solution {
public int minArray(int[] numbers) {
int low = 0;
int high = numbers.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (numbers[mid] < numbers[high]) {
high = mid;
} else if (numbers[mid] > numbers[high]) {
low = mid + 1;
} else {
// 相等的情况 只需要 -1 即可
high -= 1;
}
}
return numbers[low];
}
}
剑指 Offer II 069. 山峰数组的顶部
https://leetcode-cn.com/problems/B1IidL/
求波峰和波谷
class Solution {
public int peakIndexInMountainArray(int[] arr) {
if (arr == null) {
return 0;
}
int left = 0;
int right = arr.length - 1;
int resIndex = -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] > arr[mid + 1]) {
right = mid - 1;
resIndex = mid;
} else {
left = mid + 1;
}
}
return resIndex;
}
}