LeetCode + 《剑指Offer II》刷题笔记。
二分查找
关于left<=right:
当left等于right时，查找范围是长度为1的子数组。长度为1的子数组仍然是一个有效的查找范围，但当left大于right时这两个下标就不能形成一个有效的查找返回，因此while循环的条件是left小于或等于right。
068. 查找插入位置
剑指 Offer II 068. 查找插入位置
可以将目标值t是否在数组中出现的两种情况统一起来，即查找满足两个条件的位置：一是该位置上的数字大于或等于t，二是该位置的前一个数字小于t。
有两种情况需要特别注意：
1、当mid等于0时如果nums[mid]依然大于目标值target，则意味着数组中的所有数字都比目标值大，应该返回0。
2、当数组中不存在大于或等于目标值target的数字时，那么target应该添加到数组所有值的后面，即返回数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]>=target){
//如果同时满足nums[mid]≥target并且nums[mid-1]＜target
//那么mid就是符合条件的位置，返回mid即可。
if(mid==0 || nums[mid-1]<target){
return mid;
}
right=mid-1;
}else{
left=mid+1;
}
}
return nums.size();
}
};
|
069. 山峰数组的顶部
剑指 Offer II 069. 山峰数组的顶部
山峰数组中的最大值是数组中唯一一个比它左右两边数字都大的数字。位于最大值前面的数字（除第1个数字之外）总是比它前一个数字大但比它后一个数字小，位于最大值后面的数字（除最后一个数字之外）总是比它后一个数字大但比它前一个数字小。
在一个长度为n的山峰数组中，由于第1个数字和最后一个数字都不可能是最大值，因此初始查找范围为数组下标从1到n-2的部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left=1,right=arr.size()-2;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid]>arr[mid-1] && arr[mid]>arr[mid+1]){
return mid;
}else if(arr[mid]>arr[mid-1]){
//即arr[mid-1]<arr[mid] && arr[mid]<arr[mid+1]
//这个数字位于数组递增的部分，数组的最大值在后面
left=mid+1;
}else{
//即arr[mid-1]>arr[mid] && arr[mid]>arr[mid+1]
//这个数字位于数组递减的部分，数组的最大值在前面
right=mid-1;
}
}
return -1;
}
};
|
070. 排序数组中只出现一次的数字
剑指 Offer II 070. 排序数组中只出现一次的数字
在一个排序数组中，如果所有数字都出现了两次，那么将数组中的数字每两个分成一组，每组的两个数字都是相等的。但如果在数组中添加一个只出现一次的数字，那么这个规律就会被打破。例如，在数组[1，1，2，2，3，4，4，5，5]中，如果将两个数字分成一组，可以分成（1，1）、（2，2）、（3，4）和（4，5），以及最后还剩下的数字5。在这几组数字中，前两组的数字分别相同，但后面两组的数字就不相同。
数组中的数字每两个分成一组，最初的若干组的两个数字都是相同的。但遇到了只出现一次的数字之后，情况发生变化。这个只出现一次的数字和后面的数字结合成一组，导致后面所有出现两次的数字都被分到两个不同的组，即后面所有组的两个数字都不相同。由此可见，只出现一次的数字正好是第1个两个数字不相等的分组的第1个数字。
将数组中的数字每两个分为一组。先找出位于中间的一组，确定这一组的两个数字是否相同。如果两个数字相同，那么那个只出现一次的数字一定在它的后面，因此接着查找它的后半部分。如果两个数字不相同，那么接着检查这一组是不是第1组两个数字不相同的分组。如果是第1组，那么这一组的第1个数字就是只出现一次的数字。如果不是第1组，那么第1组一定在它的前面，因此接着查找它的前半部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left=0,right=nums.size()/2;
while(left<=right){
int mid=(left+right)/2;
//查找范围中间编号为mid的分组，这个分组的第1个数字在数组中的下标为i
int i=mid*2;
if(i<nums.size()-1 && nums[i]!=nums[i+1]){
//mid==0要放在nums[i-2]==nums[i-1]之前
//否则[1,2,2,3,3]用例执行出错
//因为mid=0时,i=0,i-2和i-1就会出错
if(mid==0 || nums[i-2]==nums[i-1]){
return nums[i];
}
right=mid-1;
}else{
left=mid+1;
}
}
return nums[nums.size()-1];
}
};
|
如果数组的长度是n（n为奇数），每两个数字分成一组，则可以分成n/2+1组，最后一组只有一个数字。把这些分组从0开始编号，那么编号为0～n/2。在上述代码中，left是查找范围内的第1个分组的编号，right是查找范围内的最后一个分组的编号。
071. 按权重生成随机数
剑指 Offer II 071. 按权重生成随机数
072. 求平方根
剑指 Offer II 072. 求平方根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int mySqrt(int x) {
int left=1,right=x;
while(left<=right){
int mid=left+(right-left)/2;
if(mid<=x/mid){
if((mid+1)>x/(mid+1)) return mid;
else left=mid+1;
}else{
right=mid-1;
}
}
return 0;
}
};
|
- 时间复杂度：O(log x)，即为二分查找需要的次数
- 空间复杂度：O(1)
34.Find First and Last Position of Element in Sorted Array
solution 1:
First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34
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
|
class Solution {
public:
int binarySearch(vector<int>& nums,int target,bool leftBias){
int left=0,right=nums.size()-1;
int res=-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]>target){
right=mid-1;
}else if(nums[mid]<target){
left=mid+1;
}else{
res=mid;
if(leftBias){
right=mid-1;
}else{
left=mid+1;
}
}
}
return res;
}
vector<int> searchRange(vector<int>& nums, int target) {
int left=binarySearch(nums,target,true);
int right=binarySearch(nums,target,false);
return vector<int>{left,right};
}
};
|
solution 2:
LeetCode Find First and Last Position of Element in Sorted Array Solution Explained - Java
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
34
35
36
|
class Solution {
public:
int lower_bound(vector<int>& nums,int target){
int left=0,right=nums.size()-1;
int index=-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]>=target){
right=mid-1;
}else{
left=mid+1;
}
if(nums[mid]==target) index=mid;
}
return index;
}
int upper_bound(vector<int>& nums,int target){
int left=0,right=nums.size()-1;
int index=-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]<=target){
left=mid+1;
}else{
right=mid-1;
}
if(nums[mid]==target) index=mid;
}
return index;
}
vector<int> searchRange(vector<int>& nums, int target) {
int left=lower_bound(nums,target);
int right=upper_bound(nums,target);
return vector<int>{left,right};
}
};
|
solution 3:
lower_bound和upper_bound函数
lower_bound() 函数用于在指定区域内查找不小于（大于等于）目标值的第一个元素。
upper_bound() 函数用于在指定范围内查找大于目标值的第一个元素。
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
34
35
|
class Solution {
public:
int lower_bound(vector<int>& nums,int target){
int left=0,right=nums.size();
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>=target){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
int upper_bound(vector<int>& nums,int target){
int left=0,right=nums.size();
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]>target){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
vector<int> searchRange(vector<int>& nums, int target) {
int left=lower_bound(nums,target);
int right=upper_bound(nums,target)-1;
if(left<=right && right<nums.size() && nums[left]==target && nums[right]==target){
return vector<int>{left,right};
}
return vector<int>{-1,-1};
}
};
|
658 Find K Closest Elements
Sorting
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
sort(arr.begin(),arr.end(),[x](int a,int b)->bool{
return abs(a-x)<abs(b-x) || (abs(a-x)==abs(b-x) && a<b);
});
sort(arr.begin(),arr.begin()+k);
return vector<int>(arr.begin(),arr.begin()+k);
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)，排序需要 O(log n) 的栈空间。
Binary Search+Two Pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
//lower_bound 大于等于x的第1个元素 --> 下标
int right=lower_bound(arr.begin(),arr.end(),x)-arr.begin();
int left=right-1;
while(k--){
if(left<0){
right++;
}else if(right>=arr.size()){
left--;
}else if(abs(arr[left]-x)<=abs(arr[right]-x)){
left--;
}else{
right++;
}
}
return vector<int>(arr.begin()+left+1,arr.begin()+right);
}
};
|
-
时间复杂度：O(log n+k)
-
空间复杂度：O(1)
将窗口大小设置为固定K
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left=0,right=arr.size()-k;
while(left<right){
int mid=left+(right-left)/2;
if(x-arr[mid]>arr[mid+k]-x){
left=mid+1;
}else{
right=mid;
}
}
return vector<int>(arr.begin()+left,arr.begin()+left+k);
}
};
|
- 时间复杂度：O( log(n-k)+k )
- 空间复杂度：O(1)
Heap(Priority Queue)
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
brute-force
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
|
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
double median;
int m=nums1.size(),n=nums2.size();
vector<int> v;
int i=0,j=0;
while(i<m && j<n){
if(nums1[i]<nums2[j]){
v.push_back(nums1[i++]);
}else{
v.push_back(nums2[j++]);
}
}
while(i<m){
v.push_back(nums1[i++]);
}
while(j<n){
v.push_back(nums2[j++]);
}
int index=(m+n)/2;
if((m+n)%2==0){
median=((v[index-1]+v[index])/2.0);
}else{
median=v[index];
}
return median;
}
};
|
- 时间复杂度：O(m+n)
- 空间复杂度：O(m+n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
}
}
|
binary search
- 时间复杂度：O(log(m+n))
- 空间复杂度：O(1)
- 时间复杂度：O( log min(m,n) )
- 空间复杂度：O(1)
Author
Anjana
LastMod
2022-01-25
License
原创文章，如需转载请注明作者和出处。谢谢！