Median of Two Sorted Arrays

Posted on |

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

思路：

用两个角标i和j,通过比较nums1和nums2的大小进行遍历。  
另外设置一个medCount来记录中位数角标。  
再考虑长度为奇数与偶数两种情况。
在LeetCode的上submit后，单独考虑一个数组为空的话，运行速度骤降到32ms(beat 40%->81%)  

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
  class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int num1 = nums1.length;
        int num2 = nums2.length;
        if(num1 == 0){
            if(num2%2 == 0){
                double result = (nums2[num2/2]+nums2[num2/2-1])*1.0/2.0;
                return result;
            }
            return nums2[num2/2];
        }
        if(num2 == 0){
            if(num1%2 == 0){
                double result = (nums1[num1/2]+nums1[num1/2-1])/2.0;
                return result;
            }
            return nums1[num1/2];
        }
        int isOdd = (num1+num2)%2;
        double result = 0;
        double tempResult = 0;
        int medCount = 0;
        int i=0;
        int j=0;
        int move1 = 0;
        int move2 = 0;
        while(true){
            tempResult = result;
            if(move1 == 1){
                result = nums1[i];
                i++;
                medCount++;
            }else if(move2 == 1){
                result = nums2[j];
                j++;
                medCount++;
            }else{
                if(nums1[i]>=nums2[j]){
                    result = nums2[j];
                    j++;
                    medCount++;
                }else
                if(nums1[i]<=nums2[j]){
                    result = nums1[i];
                    i++;
                    medCount++;
                }
            }
            if(i==num1){
                move2 = 1;
            }
            if(j==num2){
                move1 = 1;
            }
            if(isOdd == 1 && medCount == (num1+num2)/2+1){
                break;
            }
            if(isOdd == 0 && medCount == (num1+num2)/2+1){
                result = (tempResult + result)/2;
                break;
            }
        }
        return result;
    }
    
}