Qi

Cogito ergo sum

0%

leetcode 4 Solution

发表于 更新于 分类于 248 1 分钟

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package com.demo.s4;

/**
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if(nums1.length > nums2.length) {
                return findMedianSortedArrays(nums2, nums1);
            }
            int m = nums1.length;
            int n = nums2.length;
            int left = 0;
            int right = m;
            // i + j = m-i + n -j -1  j = m+n+1/2 -i m<n
            int median1 = 0;
            int median2 = 0;
            while(left <= right) {
                int i = (left + right) / 2;
                int j = (m + n + 1) / 2 - i;
                int mediana1 = (i == 0 ? Integer.MIN_VALUE : nums1[i-1]);
                int mediana2 = (i == m ? Integer.MAX_VALUE : nums1[i]);
                int medianb1 = (j == 0 ? Integer.MIN_VALUE : nums2[j-1]);
                int medianb2 = (j == n ? Integer.MAX_VALUE : nums2[j]);
                if(mediana1 <= medianb2) {
                    median1 = Math.max(mediana1, medianb1);
                    median2 = Math.min(mediana2, medianb2);
                    left = i + 1;
                } else {
                    right  = i - 1;
                }
            }
            return ( m + n) %2==0? (median1 + median2) / 2.0 : median1;
        }

}