第 4 天
查找算法（简单）
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
题解思路：原地交换、辅助空间
原地交换：不断的将数组元素重新排放，使得 nums[i] == i，直到找到重复元素，或全部摆放完成。
class Solution {
public int findRepeatNumber(int[] nums) {
int i = 0;
while (nums.length > i) {
if (nums[i] == i) {
i ++;
continue;
}
if (nums[nums[i]] == nums[i]) {
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
return -1;
}
}
复杂度：时间 O(n) 空间 O(1)
辅助空间：利用 Set 结构中没有重复元素的特点，找到重复元素，每次添加进 Set 前判断是否已经存在该元素
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> dic = new HashSet<>();
for (int num : nums) {
if (dic.contains(num)) {
return num;
}
dic.add(num);
}
return 1;
}
}
复杂度：时间 O(n) 空间 O(n)
剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
题解思路：一次二分查找、两次二分查找
一次二分查找：首先利用二分查找到该元素最左边的一个，然后遍历该元素右边，统计出现次数
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int count = 0;
while (left < right) {
int mid = (right + left) / 2;
if (nums[mid] >= target) {
right = mid;
}
if (nums[mid] < target) {
left = mid + 1;
}
}
while (left < nums.length) {
if (nums[left] == target) {
count ++;
}
left ++;
}
return count;
}
}
复杂度：时间 O(log n) 空间 O(1)
二次二分查找：左右两边分别遍历，找到左右两边的边界，做差即可
class Solution {
public int search(int[] nums, int t) {
int n = nums.length;
if (n == 0) return 0;
int a = -1, b = -1;
// 二分出左边界
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= t) r = mid;
else l = mid + 1;
}
if (nums[r] != t) return 0;
a = r;
// 二分出右边界
l = 0; r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (nums[mid] <= t) l = mid;
else r = mid - 1;
}
if (nums[r] != t) return 0;
b = r;
return b - a + 1;
}
}
复杂度：时间 O(log n) 空间 O(n)
剑指 Offer 53 - II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
题解思路：二分查找
二分查找：二分法判断缺失值在左右哪一边
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == mid) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left;
}
}
