58同城建筑招聘网最新招聘,seo是啥职业,好看的个人网站主页,成品短视频网站源码搭建文章目录 前言1. 有序数组转二叉搜索树2. 寻找连个正序数组的中位数总结 前言 提示#xff1a;有时候#xff0c;我感觉自己一辈子活在两个闹钟之间#xff0c;早上的第一次闹钟#xff0c;以及5分钟之后的第二次闹钟。 --奥利弗萨克斯《意识的河流》 每个专题都有简单题有时候我感觉自己一辈子活在两个闹钟之间早上的第一次闹钟以及5分钟之后的第二次闹钟。 --奥利弗·萨克斯《意识的河流》 每个专题都有简单题有难的题目。这里就介绍两道有挑战的题一道是关于二叉搜索树的一道是从两个数组中寻找中位数的。 1. 有序数组转二叉搜索树
参考题目介绍108. 将有序数组转换为二叉搜索树 - 力扣LeetCode 理论上如果要构造二叉搜索树可以以升序序列中的任意一个元素作为根节点以该元素左边的升序序列构建左子树以该元素的右边的升序序列构建右子树这样得到的树就是一棵二叉搜索树。本体要求高度平衡一次我们需要选择升序序列的中间元素作为根节点其本质就是二分查找的过程。
话不多说看代码 /*** 升序数组转二叉搜索树* param nums* return*/public static TreeNode sortedArrayToBST(int[] nums) {return dfs(nums,0,nums.length - 1);}private static TreeNode dfs(int[] nums, int left, int right) {if (left right){return null;}// 处理节点 总是选择中间位置左边的数字作为根节点int mid left ((right - left) 1);TreeNode root new TreeNode(nums[mid]);root.left dfs(nums,left,mid - 1);root.right dfs(nums,mid 1,right);return root;}除了通过数组构造是否可以通过一个个插入的方式来实现呢当然可以。那如果从中间删除一个元素呢
推荐一下题目⭐⭐⭐⭐⭐
701. 二叉搜索树中的插入操作 - 力扣LeetCode
450. 删除二叉搜索树中的节点 - 力扣LeetCode
2. 寻找连个正序数组的中位数
参考题目介绍4. 寻找两个正序数组的中位数 - 力扣LeetCode 对于本题最值观的思路有一下两种
使用并归的方式合并两个有序数组得到一个大的有序数组。大的有序数组中间的元素即使中位数。这种方式的时间复杂度为O(m n),空间复杂度为O(m n)直接找到中位数。由于两个数组的长度已知因此中位数对应的两个数组的下标之和也是已知的。维护两个指针初始分别指向两个数组的下标00的位置每次将指针指向较小的指针后移一位如果指针已经达到数组末尾只需要移动另一个数组指针直到到达中位数的位置。这样的方式可以将空间复杂度降低至O(1)但是时间复杂度仍是O(m n).
如何把时间复杂度降低至O(log(mn))呢如果对时间复杂度的要求是log通常都要考虑二分快排或者堆三个方面。而对于有序的序列通常要优先考虑使用二分来解决。
如果要使用二分核心问题是基于什么规则将数据砍掉一半。而本题是两个序列所以我们的核心问题是如何从两个序列中分别砍半图示k (m n) 1; 根据中位数的定义当 m n是奇数时中间的两个序列数组的第(m n) 1个元素当 m n是偶数时中间是两个有序数组中的第(m n) 1个元素和第((m n) 1) 1的平均值。因此这道题可以转换为寻找两个有序数组中的第k小的数其中k为(m n) 1或者((m n) 1) 1
假设两个有序数组分别是LA和LB。要找到第k个元素我饿们可以比较LA[k / 2 - 1]和LB[k / 2 -1]。由于LA[k / 2 - 1]和LB[k / 2 -1]的前面分别是LA[k / 2 - 2]和LB[k / 2 -2]即k / 2 - 1个元素对于LA[k / 2 - 1]和LB[k / 2 -1]中的最小值最多只会有[k / 2 - 1] [k / 2 -1] k - 2个元素比它小那么它不就是我们要的第k小的数了。
因此我们可以总结一下
如果LA[k / 2 - 1] LB[k / 2 -1]则比LA[k / 2 - 1]小的最多有LA的前面k / 2 - 1个数和LB前面k / 2 - 1个数即比LA[k / 2 - 1]小的数最多只有k - 2个因此LA[k / 2 - 1]不可能是第k个数所以LA[0]到LA[k / 2 - 1]也不可能是第k个数可以全部舍弃掉如果LA[k / 2 - 1] LB[k / 2 -1]则可以推理排除LB[0]到LB[k / 2 - 1]也不可能是第k个数可以全部舍弃掉如果LA[k / 2 - 1] LB[k / 2 -1]则可以归入第一种情况处理。 可以看到比较LA[k / 2 - 1] LB[k / 2 -1]之后可以排除k / 2个不可能是第k小的数查找范围缩小了一半。同时我们将排除后的数组上继续进行二分查找的话并且根据我们排除的个数减少k的值这是因为我们排除的数都不大于第k小的数。
注意一下边界处理
如果LA[k / 2 - 1] 或者LB[k / 2 -1]越界那么我们可以以选取对应数组中的最后一个元素。这种情况下我们必须根据排除数的个数减少k的值而不是直接将k减去k / 2.如果k 1 我们只需要返回两数组的首元素的最小值即可。
分析了这么多怎么写这个代码呢 /*** 两个有序数组找中间值* param nums1* param nums2* return*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 nums1.length,length2 nums2.length;int totalLength length1 length2;if (totalLength % 2 1){int midIndex totalLength 1;double median getKthElement(nums1,nums2,midIndex 1);return median;}else{int midIndex1 (totalLength 1) - 1;int midIndex2 (totalLength 1);double median (getKthElement(nums1,nums2,midIndex1 1) getKthElement(nums1,nums2,midIndex2 1)) / 2.0;return median;}}private double getKthElement(int[] nums1, int[] nums2, int k) {int length1 nums1.length,length2 nums2.length;int index1 0, index2 0;int kthElement 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 1;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;}}}总结
提示二分进阶二分搜索中序遍历递归算法分治思想
