在 Java 中查找两个排序数组的中位数-java教程-PHP中文网

在 Java 中查找两个排序数组的中位数

王林

发布： 2024-07-22 17:19:19

转载

748人浏览过

在 java 中查找两个排序数组的中位数

java教程
java 文件

介绍

求两个已排序数组的中位数的问题是一个经典的编码面试问题。挑战在于有效地找到中位数，时间复杂度为 o(log(min(m, n)))，其中 m 和 n 是两个数组的大小。在本文中，我们将介绍一个使用二分搜索来实现这种效率的 java 解决方案。

问题陈述

给定两个排序数组 nums1 和 nums2，找到这两个排序数组的中位数。整体运行时复杂度应该是 o(log(min(m, n)))，其中 m 和 n 是两个数组的大小。

方法

为了解决这个问题，我们对两个数组中较小的一个使用二分搜索方法。目标是对两个数组进行分区，使左半部分包含小于或等于右半部分元素的所有元素。这是一步一步的解释：

确保 nums1 是较小的数组：为了更容易进行二分查找，请确保 nums1 是较小的数组。
执行二分查找：对 nums1 使用二分查找来找到正确的分区。
分区：对两个数组进行分区，使左侧包含较低的元素，右侧包含较高的元素。
计算中位数：根据分区，计算中位数。

解决方案

这是该解决方案的详细 java 实现：

网龙b2b仿阿里巴巴电子商务平台

本系统经过多次升级改造，系统内核经过多次优化组合，已经具备相对比较方便快捷的个性化定制的特性，用户部署完毕以后，按照自己的运营要求，可实现快速定制会费管理，支持在线缴费和退费功能财富中心，管理会员的诚信度数据单客户多用户登录管理全部信息支持审批和排名不同的会员级别有不同的信息发布权限企业站单独生成，企业自主决定更新企业站信息留言、询价、报价统一管理，分系统查看分类信息参数化管理，支持多样分类信息，

查看详情

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Edge cases
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                // Correct partition
                if ((x + y) % 2 == 0) {
                    return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                } else {
                    return Math.max(maxX, maxY);
                }
            } else if (maxX > minY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

登录后复制

解释

初始化：确保nums1是较小的数组。
二分查找：对 nums1 执行二分查找以找到正确的分区。
分区和中位数计算：计算左侧元素的最大值和右侧元素的最小值以找到中位数。

结论

这种二分搜索方法提供了一种有效的解决方案来查找两个排序数组的中位数。通过在较小的数组上利用二分搜索，该解决方案实现了 o(log(min(m, n))) 的时间复杂度，使其适合大型输入数组。

立即学习“Java免费学习笔记（深入）”；

以上就是在 Java 中查找两个排序数组的中位数的详细内容，更多请关注php中文网其它相关文章！