淮南装饰公司网站建设,深度网营销型网站建设,seo案例,广州企业建设网站LeetCode力扣双指针题目
主要提供了力扣热题第四题#xff0c;使用js#xff0c;复杂度O(log(mn))#xff0c;寻找两个正序数组的中位数。
题目解析
题目要求在两个已排序数组 nums1 和 nums2 中找到它们的中位数。为了满足时间复杂度要求 O(log (mn))#xff0c;可以采…LeetCode力扣双指针题目
主要提供了力扣热题第四题使用js复杂度O(log(mn))寻找两个正序数组的中位数。
题目解析
题目要求在两个已排序数组 nums1 和 nums2 中找到它们的中位数。为了满足时间复杂度要求 O(log (mn))可以采用双指针的方法合并这两个数组然后计算中位数。
思路
首先代码检查 nums1 和 nums2 的长度确保 nums1 总是较短的数组。如果 nums1 的长度大于 nums2则通过递归调用 findMedianSortedArrays 函数将它们的顺序反转以确保 nums1 始终是较短的数组。
获取 nums1 和 nums2 的长度分别赋值给 x 和 y。
初始化两个指针 low 和 high它们将用于执行二分查找。low 初始为0high 初始为 x即 nums1 的长度。
进入一个循环循环条件是 low 小于等于 high。
在每次循环迭代中计算 partitionX 和 partitionY这两个值将用于将数组分成左右两部分。partitionX 表示将 nums1 分成左右两部分的分界点而 partitionY 表示将 nums2 分成左右两部分的分界点。这些分界点是通过位运算和数组长度计算得出的。
根据分界点获取左右两部分的最大值和最小值。maxX 和 minX 表示 nums1 中左右两部分的最大值和最小值而 maxY 和 minY 表示 nums2 中左右两部分的最大值和最小值。
接着代码检查最大值和最小值是否满足中位数的条件即 maxX minY 和 maxY minX。如果满足这些条件说明找到了中位数的位置。
如果总元素个数是偶数(x y) % 2 0则中位数是左右两部分的最大值和最小值的平均数如果总元素个数是奇数中位数是最大值中的较大值。
如果没有找到中位数的位置根据情况更新 low 或 high以继续二分查找。
最终如果循环结束后仍然没有找到中位数的位置代码会抛出一个错误表示输入的数组不是有序的。
代码
function findMedianSortedArrays(nums1, nums2) {if (nums1.length nums2.length) {return findMedianSortedArrays(nums2, nums1);}const x nums1.length;const y nums2.length;let low 0;let high x;while (low high) {const partitionX (low high) 1;const partitionY ((x y 1) 1) - partitionX;const maxX (partitionX 0) ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];const maxY (partitionY 0) ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];const minX (partitionX x) ? Number.POSITIVE_INFINITY : nums1[partitionX];const minY (partitionY y) ? Number.POSITIVE_INFINITY : nums2[partitionY];if (maxX minY maxY minX) {if ((x y) % 2 0) {return (Math.max(maxX, maxY) Math.min(minX, minY)) / 2;} else {return Math.max(maxX, maxY);}} else if (maxX minY) {high partitionX - 1;} else {low partitionX 1;}}throw new Error(Input arrays are not sorted.);
}代码解析 ((x y 1) 1) - partitionX这段代码是什么意思 ((x y 1) 1) - partitionX 这段代码用于计算 partitionY即将第二个数组 nums2 分成左右两部分的分界点。让我解释一下这个表达式的含义
x 是第一个数组 nums1 的长度。y 是第二个数组 nums2 的长度。partitionX 是将第一个数组 nums1 分成左右两部分的分界点。
现在来逐步解释这个表达式 x y 1首先将两个数组的长度相加并加1。这是因为在计算中位数时需要考虑总的元素个数是否为奇数还是偶数。 1然后对上述结果进行右移一位相当于除以2。这是因为中位数是将数组分成两部分左半部分和右半部分因此需要将总长度分为两半。 - partitionX最后从上述结果中减去 partitionX。partitionX 表示将第一个数组 nums1 分成左右两部分的分界点。减去 partitionX 的目的是确定第二个数组 nums2 分成左右两部分的分界点 partitionY。
这个表达式的目的是计算如何将两个数组分成左右两部分以满足中位数的条件。它考虑了两个数组的长度以确保正确计算中位数的位置。在这种二分查找算法中partitionX 和 partitionY 的计算是关键因为它们指导着如何在两个数组中查找中位数的位置。 if (maxX minY maxY minX) {这段代码是什么意思 maxX 表示第一个数组 nums1 中分界点 partitionX 左侧部分的最大值或者在 partitionX 为0时为负无穷大。minY 表示第二个数组 nums2 中分界点 partitionY 右侧部分的最小值或者在 partitionY 为 y 时为正无穷大。maxY 表示第二个数组 nums2 中分界点 partitionY 左侧部分的最大值或者在 partitionY 为0时为负无穷大。minX 表示第一个数组 nums1 中分界点 partitionX 右侧部分的最小值或者在 partitionX 为 x 时为正无穷大。
这个条件 maxX minY maxY minX 检查以下情况是否成立 maxX 小于等于 minY即第一个数组左侧部分的最大值小于等于第二个数组右侧部分的最小值。 maxY 小于等于 minX即第二个数组左侧部分的最大值小于等于第一个数组右侧部分的最小值。
如果这两个条件都成立意味着已找到中位数的位置因为左侧部分的元素都小于或等于右侧部分的元素。这是中位数的定义。
在满足这些条件的情况下根据总元素个数是奇数还是偶数代码返回相应的中位数值。如果总元素个数是偶数中位数是左右两部分的最大值和最小值的平均数如果总元素个数是奇数中位数是最大值中的较大值。
这个条件判断是整个算法中的核心用于确定中位数的位置。如果条件不成立代码将根据情况更新 low 或 high以继续二分查找直到找到中位数的位置
总结
希望本文会对你有所帮助如果有任何疑问可以留言与我沟通。
