算法通关村第九关|黄金挑战|有序数组转为二叉搜索树&寻找两个正序数组的中位数

1.有序数组转为二叉搜索树

原题：力扣108.

高度平衡二叉树：每个节点的左右两个子树的高度差的绝对值不超过1。

本题要求高度平衡，所以选择中间元素作为根节点。因为是升序数组，所以可以直接构造出搜索树。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, num.length - 1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
        // left < right 时构造节点
        // left = right 时构造叶子节点
        // left > right 时返回null
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.寻找两个正序数组的中位数

原题：力扣4.

要求时间复杂度为O(log(m+n))，且为有序数组，容易想到使用二分法。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLenght / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    // k 不是数组下标，是一段长度
    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = num2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 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

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤
个人主页：星不易 ❤
算法通关村专栏：不易|算法通关村 ❤