leetcode04-寻找两个有序数组的中位数

男娘i 2024-04-17 16:48 66阅读 0赞

*  [寻找两个有序数组的中位数][Link 1]
    
     *  [题目描述][Link 2]
     *  [code][]

# 寻找两个有序数组的中位数 #

## 题目描述 ##

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
    nums2 = [2]
    
    则中位数是 2.0
    示例 2:
    
    nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5

## code ##

package com.wangyg.leetcode;
    
    import org.junit.Test;
    
    public class Test04 {
        @Test
        public void test() {
            Solution s = new Solution();
            int[] num1 = new int[]{1, 2};
            int[] num2 = new int[]{3, 4};
            System.out.println(s.findMedianSortedArrays(num1, num2));
        }
    
        class Solution {
            public double findMedianSortedArrays(int[] A, int[] B) {
                int m = A.length; //A的长度
                int n = B.length; //B的长度
                if (m > n) { // m指向小的数组， n 指向大的数组
                    int[] temp = A;
                    A = B;
                    B = temp; //数组内容交换
                    int tmp = m;
                    m = n;
                    n = tmp;  //数组长度进行交换
                }
                //始终 m指向小的数组，n指向大的数组
                int iMin = 0;
                int iMax = m;  //
                int halfLen = (m + n + 1) / 2;   //m+n+1/2指向中间值
                while (iMin <= iMax) {
                    int i = (iMin + iMax) / 2;
                    int j = halfLen - i;  //最后一个
                    if (i < iMax && B[j - 1] > A[i]) {
                        iMin = i + 1; // i is too small
                    } else if (i > iMin && A[i - 1] > B[j]) {
                        iMax = i - 1; // i is too big
                    } else { // i is perfect
                        int maxLeft = 0;
                        if (i == 0) {
                            maxLeft = B[j - 1];
                        } else if (j == 0) {
                            maxLeft = A[i - 1];
                        } else {
                            maxLeft = Math.max(A[i - 1], B[j - 1]);
                        }
                        if ((m + n) % 2 == 1) {
                            return maxLeft;
                        }
    
                        int minRight = 0;
                        if (i == m) {
                            minRight = B[j];
                        } else if (j == n) {
                            minRight = A[i];
                        } else {
                            minRight = Math.min(B[j], A[i]);
                        }
                        return (maxLeft + minRight) / 2.0;
                    }
                }
                return 0.0;
            }
        }
    }

[Link 1]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2FD1F709F9A82B433785FD4D26469BB01A%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D26d84837ec5333889d319441f264c786#%E5%AF%BB%E6%89%BE%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0
[Link 2]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2FD1F709F9A82B433785FD4D26469BB01A%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D26d84837ec5333889d319441f264c786#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0
[code]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2FD1F709F9A82B433785FD4D26469BB01A%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3D26d84837ec5333889d319441f264c786#code