力扣记录：剑指offer（6）——JZ53-58

JZ53-I 在排序数组中查找数字 I

• 先使用二分查找搜索目标数字位置，找到目标数字后再向两边计算目标数字出现的次数（优化：两次二分查找，分别找到左边界和右边界）
  • 时间复杂度O(logn)，空间复杂度O(1)

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 = left + (right - left) / 2;
            if(nums[mid] > target){
   
                right = mid - 1;
            }else if(nums[mid] < target){
   
                left = mid + 1;
            }else{
   
                //向两边搜索
                int i = mid;
                int j = mid;
                count += 1;
                while(i >= 1 && nums[i - 1] == target){
   
                    count++;
                    i--;
                }
                while(j < nums.length - 1 && nums[j + 1] == target){
   
                    count++;
                    j++;
                }
                return count;
            }
        }
        return count;
    }
    //优化
    public int search(int[] nums, int target) {
   
        //二分查找，左闭右闭
        //搜索右边界
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = 0;
        while(left <= right){
   
            int mid = left + (right - left) / 2;
            if(nums[mid] > target){
   
                right = mid - 1;
            }else if(nums[mid] <= target){
   
                left = mid + 1;
            }
        }
        if(left == 0 || nums[left - 1] != target) return 0;  //未搜索到目标值
        rightBorder = left;
        //搜索左边界
        int leftBorder = 0;
        left = 0;
        right = rightBorder;    //左边界肯定在右边界左边
        while(left <= right){
   
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target){
   
                right = mid - 1;
            }else if(nums[mid] < target){
   
                left = mid + 1;
            }
        }
        leftBorder = right;
        return rightBorder - leftBorder - 1;
    }
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

JZ53-II 0～n-1中缺失的数字

• 二分查找，二分后得到的数需要和下标一致，如果大于下标则向左边搜索（左边缺一位），如果等于下标则向右边搜索
  • 时间复杂度O(logn)，空间复杂度O(1)

class Solution {
   
    public int missingNumber(int[] nums) {
   
        //二分查找
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
   
            int mid = left + (right - left) / 2;
            if(nums[mid] > mid){
   
                right = mid - 1;
            }else{
   
                left = mid + 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

JZ54 二叉搜索树的第k大节点

• 中序遍历（二叉搜索树中序遍历递增），计数返回结果
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
   
    int res, count; //注意这里使用全局变量不容易混淆
    public int kthLargest(TreeNode root, int k) {
   
        //中序遍历的逆序右中左
        count = 0;
        reverseInorder(root, k);
        return res;
    }
    private void reverseInorder(TreeNode root, int k){
   
        if(root == null) return;
        if(count == k) return;
        reverseInorder(root.right, k);
        count++;
        if(count == k){
   
            res = root.val;
            return;
        }
        reverseInorder(root.left, k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

JZ55-I 二叉树的深度

• 前序遍历或后序遍历，到达叶子节点时计算当前深度
  • 时间复杂度O(n)，空间复杂度O(二叉树深度)

class Solution {
   
    int res;
    public int maxDepth(TreeNode root) {
   
1
2
3
4