leetcode/Problem4/Solution.java at master · gorthitk/leetcode · GitHub

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

public class Solution
{
    public double findMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int total = nums1.length + nums2.length;
        if (total % 2 == 0)
        {
            return (findKth(total / 2 + 1, nums1, nums2, 0, 0) + findKth(total / 2, nums1, nums2, 0, 0)) / 2.0;
        }
        else
        {
            return findKth(total / 2 + 1, nums1, nums2, 0, 0);
        }
    }

    public int findKth(int k, int[] nums1, int[] nums2, int s1, int s2)
    {
        if (s1 >= nums1.length)
        {
            return nums2[s2 + k - 1];
        }
        if (s2 >= nums2.length)
        {
            return nums1[s1 + k - 1];
        }
        if (k == 1)
        {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int m1 = s1 + k / 2 - 1;
        int m2 = s2 + k / 2 - 1;
        int mid1 = m1 < nums1.length ? nums1[m1] : Integer.MAX_VALUE;
        int mid2 = m2 < nums2.length ? nums2[m2] : Integer.MAX_VALUE;
        if (mid1 < mid2)
        {
            return findKth(k - k / 2, nums1, nums2, m1 + 1, s2);
        }
        else
        {
            return findKth(k - k / 2, nums1, nums2, s1, m2 + 1);
        }
    }
}