JavaScript实现获取两个排序数组的中位数算法示例

在JavaScript编程中，中位数是指一组数据按大小顺序排列后位于中间位置的数。当数据的个数为奇数时，中位数是中间的那个数；若数据个数为偶数，则中位数是中间两个数的平均值。本问题要求在两个已排序的数组`nums1`和`nums2`中找到它们合并后的中位数，并且要求算法的时间复杂度为O(log (m+n))，其中m和n分别是两个数组的长度。 我们需要理解如何在两个有序数组中寻找中位数。一种直观的方法是将两个数组合并成一个，然后排序，但这会带来较高的时间复杂度，不符合题目要求。因此，我们需要使用分治策略来降低复杂度。 分析题目给出的示例代码，虽然其思路是将`nums2`中的元素插入到`nums1`中，然后对整个数组进行排序，这会导致时间复杂度超过O(log (m+n))，但我们可以提供一个更高效的解决方案。 以下是改进的算法思路： 1. 我们需要确定哪个数组的长度较短，设较短数组为`arr1`，较长数组为`arr2`。这样可以确保在查找中位数时处理的元素数量不会超过较小数组的长度。 2. 使用二分查找法在`arr1`中找到一个位置，使得`arr1`在这个位置的左侧元素与`arr2`左侧元素的总数等于`arr1`右侧元素与`arr2`右侧元素的总数。如果`arr1`长度为n，`arr2`长度为m，那么这个位置可以表示为`(n + m + 1) / 2`。 3. 设这个位置为`index`，我们需要检查两种情况： - 如果`index`落在`arr1`内，那么中位数将是`arr1[index]`和`arr2[index - n]`的平均值（如果`arr1`和`arr2`长度均为奇数，或者`arr2`长度为偶数）或`arr1[index]`（如果`arr1`长度为偶数，`arr2`长度为奇数）。 - 如果`index`落在`arr2`内，情况类似，只是交换了数组的角色。 以下是一个符合题目要求的优化算法实现： ```javascript function findMedianSortedArrays(nums1, nums2) { let len1 = nums1.length; let len2 = nums2.length; let totalLen = len1 + len2; if (len1 > len2) { [nums1, nums2] = [nums2, nums1]; [len1, len2] = [len2, len1]; } let low = 0, high = len1; while (low <= high) { let partitionX = (low + high) >> 1; let partitionY = (totalLen + 1) / 2 - partitionX; let maxLeftX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1]; let minRightX = (partitionX === len1) ? Infinity : nums1[partitionX]; let maxLeftY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1]; let minRightY = (partitionY === len2) ? Infinity : nums2[partitionY]; if (maxLeftX <= minRightY) { if (maxLeftY <= minRightX) { // 分割位置正确 if ((totalLen & 1) === 1) { // 总长度为奇数，返回单个中位数 return (maxLeftX >= maxLeftY ? maxLeftX : maxLeftY); } else { // 总长度为偶数，返回两个中位数的平均值 return (maxLeftX + Math.min(minRightX, minRightY)) / 2; } } else { // 需要向左移动分割位置 low = partitionX + 1; } } else { // 需要向右移动分割位置 high = partitionX - 1; } } throw new Error('Invalid input arrays'); } let nums1 = [1, 2]; let nums2 = [3, 4]; console.log(findMedianSortedArrays(nums1, nums2)); ``` 这段代码使用了二分查找策略，通过不断地调整分割位置，最终找到满足条件的中位数。它的时间复杂度为O(log (m+n))，符合题目的要求。 在实际编程中，我们还需要考虑边界情况和错误处理，例如输入数组可能为空或者非有序。在上述示例中，我们假设输入都是有效的排序数组。在实际应用中，我们应添加相应的验证和异常处理机制以提高代码的健壮性。