网站开发是否交印花税,域名注册商查询工具,建网站做cpa,外贸网站如何推广出去大家好#xff0c;我是怒码少年小码。
上一篇讲了二分查找#xff0c;今天我们看看它的难度扩展。
有序数组转为二叉搜索树
LeetCode 108#xff1a;给你一个整数数组 nums #xff0c;其中元素已经按 升序 排列#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高…大家好我是怒码少年小码。
上一篇讲了二分查找今天我们看看它的难度扩展。
有序数组转为二叉搜索树
LeetCode 108给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡:二叉树是一棵满足每个节点的左右两个子树的高度差的绝对值不超过1的二叉树。 二叉搜索树的中序遍历就是有序数组相当于现在知道中序遍历的结果让你构造二叉树是不是很简单答案也有很多种但是这里限制了左右子树的高度差绝对值不能超过1答案就少了。
分析二叉搜索树的根节点的左子树上的结点的值都比根节点的值小根节点的右子树上的结点的值都比根节点的值大而根节点的左子树中的根节点也符合这一条件根节点的右子树中的根节点也符合这一条件。
所以我们可以使用int mid (left right) / 2;将数组用中间元素分出左右数组中间元素作为根节点再从左右数组中分别找出左右数组中的中间元素当作根节点的左右结点如此循环往复知道数组为空。所以这本质上就是一个二分查找。
终止条件left right。代码如下
TreeNode* helper(vectorint nums, int left, int right) {if (left right) {return nullptr;}//总是选择中间位置左边的数字为根节点int mid (left right) / 2;TreeNode* root new TreeNode(nums[mid]);//返回mid左边数组构造的左子树root-left helper(nums, left, mid - 1);//返回mid右边数组构造的右子树root-right helper(nums, mid 1, right);return root;
}TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums, 0, nums.size() - 1);
}寻找两个正序数组的中位数
LeetCode 4给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和nums2。请你找出并返回这两个正序数组的中位数 。算法的时间复杂度应该为 O(log (mn)) 。 输入nums1 [1,2] nums2 [3, 4]输出2.50000解释合并数组 [1,2,3,4], 中位数 (2 3) / 2 2.5 这道题如果没有时间复杂度的限制可以有很多种解决方法
暴力解题合并两个数组然后再遍历找到中位数。中位数就是 位于(mn)/2 k位置上的数同时遍历两个数组比较大小移动指针找到第k个大的元素。
但是很显然时间复杂度都不对想让有log 一般都要使用二分、堆和快排的方法。
接下来使用二分的方法讲解当mn为奇数中位数是有序数组的第mn)/2个元素为偶数中位数是第(mn)/2个元素和第(mn)/2 1个元素的平均值。所以这道题转化成寻找两个有序数组的第 k 小的数k为(mn)/2或者(mn)/2 1。
假如有两个有序数组nums1和nums2要找到第k个元素我们先比较nums1[k/2-1]和nums2[k/2-1]。比较完大小后有以下几种情况
如果nums1[k/2-1] nums2[k/2-1],则比nums1[k/2-1]小的数最多只有nums1的前k/2 - 1个数和nums2的前k/2 - 1个因此比其小的数最多只有k-2个因此nums1[k/2 - 1]不可能是第k个数那么便可以排除掉nums1[0]到nums1[k/2 - 1]的数也就是一次砍掉一半。 如下图中第一种情况 如果nums1[k/2-1] nums2[k/2-1],便可以排除掉nums2[0]到nums2[k/2 - 1]的数。 如下图中第二种情况 如果nums1[k/2-1] nums2[k/2-1], 则归入第一种情况处理。 如下图中第三种情况 所以我们每次都能缩小一半范围那最后我们就可以以log的时间复杂度找到我们要的中位数啦
在此之前我们还需要处理以下几个特殊情况 如果nums1[k/2 - 1] 或者 nums2[k/2 - 1]越界那我们我们可以选取其对应数组的最后一个元素。在这种情况下我们必须根据排除的个数减少k的值而不能直接将k减去k/2。 如果k1,我们只需要返回两个数组首元素的最小值就可以了。
int getKthElement(const vectorint nums1, const vectorint nums2, int k) {int m nums1.size();int n nums2.size();int index1 0, index2 0;while (true) {// 边界情况if (index1 m) {return nums2[index2 k - 1];}if (index2 n) {return nums1[index1 k - 1];}if (k 1) {return min(nums1[index1], nums2[index2]);}// 正常情况int newIndex1 min(index1 k / 2 - 1, m - 1);int newIndex2 min(index2 k / 2 - 1, n - 1);int pivot1 nums1[newIndex1];int pivot2 nums2[newIndex2];if (pivot1 pivot2) {k - newIndex1 - index1 1;index1 newIndex1 1;}else {k - newIndex2 - index2 1;index2 newIndex2 1;}}
}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int totalLength nums1.size() nums2.size();if (totalLength % 2 1) {return getKthElement(nums1, nums2, (totalLength 1) / 2);}else {return (getKthElement(nums1, nums2, totalLength / 2) getKthElement(nums1, nums2, totalLength / 2 1)) / 2.0;}
}本篇参考了这篇文章
END
最后一道题是力扣上的困难题这么说吧我觉得我像一个废物。
