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

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

思路

两次二分查找，分别找到等于$target$ 的元素的最左位置和最右位置

初始化最左位置 $first = -1$，最右位置 $last = -1$。

找最左位置：

  • 如果$nums[mid]$ 等于 $target$，暂时认为此时的位置是最左位置，令$first = mid$。再让 $right = mid - 1$，尝试查找更左的位置是否还有与 $target$ 相同的元素。
  • 如果 $nums[mid]$ 小于 $target$，查找 $mid$ 右侧的元素
  • 如果 $nums[mid]$ 大于 $target$，查找 $mid$ 左侧的元素。

找最右位置同理：

  • 如果$nums[mid]$ 等于 $target$，暂时认为此时的位置是最右位置，令$last = mid$。再让 $left = mid + 1$，尝试查找更右的位置是否还有与 $target$ 相同的元素。
  • 如果 $nums[mid]$ 小于 $target$，查找 $mid$ 右侧的元素
  • 如果 $nums[mid]$ 大于 $target$，查找 $mid$ 左侧的元素。

返回数组 $[first, last]$

复杂度

  • 时间复杂度: $O(logn)$，其中$n$为数组的长度。二分查找的时间复杂度为$O(logn)$，一共会执行两次，因此总时间复杂度为$O(logn)$。

  • 空间复杂度: $O(1)$。只需要常数空间存放若干变量。

Code

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int last = -1;
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                first = mid;
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        left = 0;
        right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                last = mid;
                left = mid + 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

         return new int[]{first, last};

    }
}

48. 旋转图像

Problem: 48. 旋转图像

思路

  • 每次选四个元素A，B，C，D顺时针旋转90°，A为左上角元素
  • D -> A, C -> D, B -> C, A -> B
  • 由于A一开始被D覆盖，为完成A -> B这一步，需要先用tmp保存A
  • 对于每个元素matrix[i] [j]，旋转前后有规律matrix[i] [j] -> matrix[j] [n-i-1]
    • 设A = matrix[i] [j]，可推导出规律
    • B = matrix[j] [n-i-1]
    • C = matrix[n-i-1] [n-j-1]
    • D = matrix[n-j-1] [i]
  • 以矩阵左上角四分之一部分的每个元素为起点执行旋转操作
    • 当矩阵大小n为偶数时，取前n/2行、前n/2列元素为起始点
    • 当n为奇数时，取前n/2行，前(n+1)/2列为起始点

复杂度

  • 时间复杂度: $O(n^2)$，其中$n$是$matrix$的边长，我们需要枚举的子矩阵大小为$O([n/2]×[(n+1)/2])=O(n^2)$
  • 空间复杂度: $O(1)$。为原地旋转。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < (n + 1) / 2; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = tmp;
            }
        }
    }
}

88 合并有序数组

Problem: 88. 合并两个有序数组

思路：双指针法

  • 定义整数a, b作为指针，开始时，指针a指向nums1的首元素，指针b指向nums2的首元素。定义一个ArrayList，名为res，作为结果。
  • 当a与b均小于等于数组的长度时，比较nums1和nums2当前的元素大小
  • 当nums1的元素小于等于nums2的元素时，将nums1的元素放入res中；否则，将nums2元素存入res。
  • 循环结束后，再次通过while循环判断a是否小于m，如果是，说明num1中有序元素个数大于nums2中有序元素个数，将nums1中剩余元素放入res。
  • 同理，对b做同样的判断。
  • 最后将res中的结果存入nums1.

Code

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 void merge(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> res = new ArrayList<>();
        int a = 0;
        int b = 0;
        while(a < m && b < n){
            if(nums1[a] <= nums2[b]){
                res.add(nums1[a]);
                a++;
            }else{
                res.add(nums2[b]);
                b++;
            }
        }

        while(a < m){
                res.add(nums1[a]);
                a++;
            }
        while(b < n){
            res.add(nums2[b]);
            b++;
        }

        for(int i = 0; i < res.size(); i++){
            nums1[i] = res.get(i);
        }
    }
}