day01 二分

34. 在排序数组中查找元素的第一个和最后一个位置

难度中等1863

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二分, 找到target之后, 向两边继续循环, 查看是否还有target

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 int[] searchRange(int[] nums, int target) {
        int []res=new int[]{-1,-1};
        int l=0,r=nums.length;
        if(nums.length==0) return res;
        while(l<r){
            int mid=l+(r-l)/2;
            if(target>nums[mid]){
                l=mid+1;
            }else if(target<nums[mid]){
                r=mid;
            }else {
                int rightOp=mid;
                res[0]=mid;
                res[1]=mid;
                while(mid>=0&&nums[mid]==nums[res[0]]){
                    res[0]=mid;
                    mid--;
                }
                while(rightOp<nums.length&&nums[rightOp]==nums[res[1]]){
                    res[1]=rightOp;
                    rightOp++;
                }
                break;
            }
        }
        return res;
    }
}

二分模板讲解

图解二分 | 最清晰易懂的讲解 | 一次性帮你解决二分边界问题【c++/java版本】 - 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

⭐️模板1

当我们将区间[l, r] ,[l,r]划分成[l, mid] [l,mid]和[mid + 1, r] [mid+1,r]时，

其更新操作是r=mid或者l = mid + 1，

计算mid时不需要加1，即mid = (l + r)/2。

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l+(r-l)/2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

⭐️模板2

当我们将区间 [l, r][l,r]划分成 [l, mid - 1][l,mid−1]和[mid, r][mid,r]时，
其更新操作是r = mid - 1或者l=mid ，

此时为了防止死循环，计算mid时需要加1，即mid = ( l + r + 1 ) /2。

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = ( l + r + 1 ) /2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

1.为什么两个二分模板mid取值不同？

对于第二个模板，当我们更新区间时，如果左边界ll更新为l=mid，此时mid的取值就应为mid = (l + r + 1)/ 2。因为当右边界r = l + 1时，此时mid = (l + r + 1)/2，下取整，mid仍为l，左边界再次更新为1=mid，相当于没有变化，while循环就会陷入死循环。因此，我们总结出来一个小技巧，当左边界要更新为l = mid时，我们就令 mid =(l + r + 1)/2，向上取整，此时就不会因为rr取特殊值r=l+1而陷入死循环了。

而对于第一个模板，如果左边界ll更新为l = mid + 1，是不会出现这样的困扰的。因此，大家可以熟记这两个二分模板，基本上可以解决99%以上的二分问题，再也不会被二分的边界取值所困扰了。

2.什么时候用模板1？什么时候用模板2？

假设初始时我们的二分区间为[l,r]，每次二分缩小区间时，如果左边界ll要更新为 l = mid，此时我们就要使用模板2，让 mid = (l + r + 1)/ 2，否则while会陷入死循环。如果左边界l更新为l = mid + 1,此时我们就使用模板1，让mid = (l + r)/2。

因此，模板1和模板2本质上是根据代码来区分的，而不是应用场景。如果写完之后发现是l=mid，那么在计算mid时需要加上1，否则如果写完之后发现是l = mid + 1，那么在计算mid时不能加1。

3.为什么模板要取while( l < r)，而不是while( l <= r)？

本质上取l<r 和l <= r是没有任何区别的，只是习惯问题，如果取l<=r，只需要修改对应的更新区间即可。

while循环结束条件是l >= r，但为什么二分结束时我们优先取r而不是l?

二分的while循环的结束条件是 l>=r，所以在循环结束时l有可能会大于r，此时就可能导致越界，因此，基本上二分问题优先取r都不会翻车。

4.实现细节：

二分查找时，首先要确定我们要查找的边界值，保证每次二分缩小区间时，边界值始终包含在内。
注意看下面的每张图，最后的答案就是红色箭头指出的位置，也是我们二分的边界值。

如果不清楚每次二分时，区间是如何更新的，可以画出和下面类似的图，

每次更新区间时，要保证边值始终包含在内，这样关于左右边界的更新就会一目了然。

第一次查找起始位置

1、二分的范围，l = 0，r = nums.size() - 1，我们去二分查找>=target的最左边界。

2、当nums[mid] >= target时，往左半区域找，r = mid

image-20220821170102010

3、当nums[mid] < target时， 往右半区域找，l = mid + 1

imgimg

4、如果nums[r] != target，说明数组中不存在目标值 target，返回 [-1, -1]。否则我们就找到了第一个>=target的位置L。

第二次查找结束位置：

1、二分的范围，l = 0，r = nums.size() - 1，我们去二分查找<=target的最右边界。

2、当nums[mid] <= target时，往右半区域找，l = mid。

imgimg

3、当nums[mid] > target时， 往左半区域找，r = mid - 1。

imgimg

4、找到了最后一个<=target的位置RR，返回区间[L,R]即可。
时间复杂度分析： 两次二分查找的时间复杂度为 O(logn)。

综上所述 , 还是选择这个模板

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l+(r-l)/2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

33. 搜索旋转排序数组

难度中等2271

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

这个题目的意思就是,

  • 给你一个原本有序的但是被旋转了一部分的数组, 也就是说数组是部分有序的

需要用O(logN) 的算法完成这个题目

  • 原本理解错题意 , 但是也能过
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
class Solution {
    public int search(int[] nums, int target) {
        //int []res=new int[nums.length];
        int k=-1;
        boolean isContains =false;
        for(int a:nums){
            k++;
            if(target==a){
                isContains=true;
                break;
            }
        }
        //if(k!=-1) {
        //System.array(res,0,nums,k,nums.length-k); // 赋值 k 开始的数字
        //System.array(res,nums.length-k,nums,0,k);  // 复制 0 开始的 前k个数字
        //}
        return isContains==true?k:-1;
    }

    public int search(int[] nums, int target) {
        int k=-1;
        boolean isContains =false;
        for(int a:nums){
            k++;
            if(target==a){
                isContains=true;
                break;
            }
        }
        return isContains==true?k:-1;
    }
}
  • 根据题意的二分解法:

74. 搜索二维矩阵

难度中等700

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

二分

思路:

  1. 遍历矩阵的每一行的第一个元素, 如果遇到了比target 大的元素就去二分查找 上一行

    • 感觉这个过程也可以优化成二分

  2. 此时找到了最大值可能位于的 line , 那么只需要二分查找target即可

    需要注意的是line的值:

    1. line ==-1
      • 此时可能是target大于矩阵中的所有的元素, 也可能是最大值在最后一行
    2. line==0
      • 此时可能是 矩阵的第一个元素就大于target
      • 也可能是 矩阵的元素位于 第一行中
    3. line 位于中间的行
      • 直接二分处理即可 , 如果没有找到直接return false

代码比较臃肿 , 但是效果还可以
image-20220820162244497image-20220820162244497

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int line=-1;
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i][0]>target){
                line=i;
                break;
            }else if(matrix[i][0]==target){
                return true;
            }
        }
        if(line==-1){// 对应 -1 可能有两种情况, 第一是 target大于所有的元素
            //第二种是 , 最大的元素在最后一行, 
            if(target>matrix[matrix.length-1][matrix[0].length-1]) //比最大值还大
                return false;
            else{
                int[]nums=matrix[matrix.length-1];
                int l=0,r=nums.length;
                while(l<r){
                    int mid=l+ (r-l)/2;
                    if(target>nums[mid]){
                        l=mid+1;
                    }else if(target<nums[mid]){
                        r=mid;
                    }else {
                        return true;
                    }
                }
                return false;
            }
        }
        if(line==0){
            int[]nums=matrix[line];
            int l=0,r=nums.length;
            while(l<r){
                int mid=l+ (r-l)/2;
                if(target>nums[mid]){
                    l=mid+1;
                }else if(target<nums[mid]){
                    r=mid;
                }else {
                    return true;
                }
            }
            return false;
        }
        int[]nums=matrix[line-1];
        int l=0,r=nums.length;
        while(l<r){
            int mid=l+ (r-l)/2;
            if(target>nums[mid]){
                l=mid+1;
            }else if(target<nums[mid]){
                r=mid;
            }else {
                return true;
            }
        }
        return false;
    }
}

缩短一下写法:

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 boolean searchMatrix(int[][] matrix, int target) {
        if(target>matrix[matrix.length-1][matrix[0].length-1]||target<matrix[0][0]) //比最大值还大 , 比最小值还小
            return false;
        int line=-1;
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i][0]>target){
                line=i;
                break;
            }else if(matrix[i][0]==target)  return true;
        }
        int []nums;
        if(line==-1) nums=matrix[matrix.length-1];
        else nums=line==0?matrix[0]:matrix[line-1];
        return binarySearch(nums,target);
    }
    boolean binarySearch(int[]nums,int target){
        int l=0,r=nums.length;
        while(l<r){
            int mid=l+ (r-l)/2;
            if(target>nums[mid])
                l=mid+1;
            else if(target<nums[mid])
                r=mid;
            else return true;
        }
        return false;
    }
}

坐标轴法

以左下角为原点, 开始按条件查找, 但是时间复杂度相对较高

image-20220820164016979image-20220820164025072image-20220820164025072

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length - 1, columns = 0;
        while (rows >= 0 && columns < matrix[0].length) {
            int num = matrix[rows][columns];
            if (num == target) {
                return true;
            } else if (num > target) {
                rows--;
            } else {
                columns++;
            }
        }
        return false;
    }
}

day02 二分

153. 寻找旋转排序数组中的最小值

难度中等812

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

  • 直接遍历维护 res

这个题与day01 的 33. 搜索旋转排序数组类似, 都是在 旋转的排序数组中的二分查找

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
class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length==1) return 0;
        for(int i=0;i<nums.length-1;i++){
            if(isPeak(nums, i)){
                return i;
            }
        }
        return -1;
    }
    public boolean isPeak(int []nums,int idx){
        if(idx==nums.length-1){
            if(nums[idx]>nums[idx-1])
                return true;
                else return false;
        }
        if(idx==0){
            if(nums[idx]<nums[idx-1])
                return true;
            else return false;
        }
        if(idx<1||idx>nums.length-2){
            return false;
        }
        return (nums[idx]>nums[idx-1]&&nums[idx]>nums[idx+1]) || (nums[idx]<nums[idx-1]&&nums[idx]<nums[idx+1]);
    }
}

162. 寻找峰值

难度中等875

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

“你可以假设 nums[-1] = nums[n] = -∞ 。”

  • 意味着第一个以及最后一个元素只需要大于他们的相邻的那一个元素即可
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length==1||nums[0]>nums[1]) return 0;
        if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
        for (int i = 1; i < nums.length-1; i++) {
            if(nums[i]>nums[i-1]&&nums[i]>nums[i+1])
                return i;
        }
        return -1;
    }
}