【每日算法Day 40】二分查找3
今天再加强一下对二分查找的熟练度，其中寻找峰值的收缩查找空间的思路值得注意。
# LeetCode 162. 寻找峰值🚩 (opens new window)
# 题目描述
峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞。
# 示例
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
2
3
# 解题思路
对于序列中的一个元素nums[i]，我们把它和nums[i+1]进行比较。如果nums[i]<nums[i+1]，则说明该元素处于升序列中，其右侧（不包括本身）一定存在至少一个极大值；否则该元素处于降序列其左侧（包括本身）一定存在至少一个极大值。就这样逐渐缩小搜索区间，当区间长度为1时该点就一定是极大值。
至于为什么和右侧元素比较而不是和左侧元素，因为我们一般取mid=(left+right)/2，当right=left+1时，mid=left，这时和右侧比不会越界，和左侧比会越界。
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right=mid;
}
}
return left;
}
2
3
4
5
6
7
8
9
10
11
12
13
# LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)
# 题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
# 示例
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
2
# 解题思路
这一题就是我们在二分查找1中学习过的，寻找目标数以及左右边界的问题，现在来复习一遍。
public int[] searchRange(int[] nums, int target) {
int[] result=new int[]{-1,-1};
int left=0,right=nums.length-1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (nums[mid] == target) {
right=mid-1;//往左搜索，锁定右边界
} else if (nums[mid] > target) {
right=mid-1;
} else if (nums[mid] < target) {
left=mid+1;
}
}
if (left < nums.length && nums[left] == target)
result[0] = left;
left=0;
right=nums.length-1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (nums[mid] == target) {
left=mid+1;//往右搜索，锁定左边界
} else if (nums[mid] > target) {
right=mid-1;
} else if (nums[mid] < target) {
left=mid+1;
}
}
if (left > 0 && nums[left - 1] == target)
result[1]=left-1;
return result;
}
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
时间复杂度为O(2*logn)，为找左右边界执行了两次二分查找。有许多冗余代码，可以封装成一个方法，不过时间复杂度并不会降低。此外，在第一次找到目标值时再调用方法查找左边界和右边界这样能够减少重复搜索的步骤（需要传入当时的边界状态）。
# LeetCOde 349. 两个数组的交集
# 题目描述
给定两个数组，编写一个函数来计算它们的交集。
# 示例
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
2
# 解题思路
下面计算空间复杂度时不考虑存放结果容器的消耗。
可以使用空间换时间，即用一个HashSet储存一个数组中唯一的元素，然后遍历另一个数组，Hash Set中含有该元素则加入到结果集中。不过将数组转换成Set需要O(nums1)的时间，遍历另一个数组需要O(nums2)的时间，空间复杂度为O(nums1)。
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> res = new HashSet<>();
for(int i:nums1){
set.add(i);
}
for(int i:nums2){
if(set.contains(i))
res.add(i);
}
int[] ans=new int[res.size()];
int index=0;
for (Integer i : res) {
ans[index++]=i;
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
也可以对其中一个数组进行排序，再遍历另一个数组中的数，在前者中二分查找该数，找到就加入到结果集。该方法时间复杂度为O(nlogn)+O(n)，空间复杂度为O(1)。
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> result = new HashSet<>();
Arrays.sort(nums1);
for (int target : nums2) {
if (Arrays.binarySearch(nums1, target)>=0) {
result.add(target);
}
}
int[] ans=new int[result.size()];
int index=0;
for (Integer i : result) {
ans[index++]=i;
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15