0%

Leetcode004 Median of Two Sorted Arrays

Posted on In Valine:

Problem:

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

Intuition:

leetcode里遇到的第一道标签为hard的题，然后就直接用暴力方法硬解出来了。跑出来时间复杂度（超过100%）和空间复杂度(超过87.5%)都比标答要好，所以采用原方法。

其实这个题思路很直接，要我找中位数，我只要把算中位数的两个数leftNum,rightNum都算出来即可。下面谈谈比较容易出问题的地方：

1.我们一点一点取数取到中位数的时候很有可能其中一个数组已经被我们取光了。而这个数组是哪个我们事先并不知道。直观上可能会认为短的数组会先被取完，但这个是不对的。如果较短的数组存的都是较大的数，那么长的数组也可能被先取完。所以往哪个数组补元素（本题的应用场景要求补正无穷）必须运行时才能决定。

2.写for循环的时候第二个数是和循环次数相等，而数组下标是从0开始，所以如果我们要从数组的第一个元素跑到数组下标所对应的元素都话，还应该再加1。这个点很容易犯错。

Solution:

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
   public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double ans = 0;
        //leftIndex表示的是中位数中计算平均数时较小的数在s1和s2合并后整个数组中的下标
        //leftIndex表示的是中位数中计算平均数时较大的数在s1和s2合并后整个数组中的下标
        int totalLength=nums1.length+nums2.length;
        int leftIndex=0;
        int rightIndex=0;
        if(totalLength%2==1){
            leftIndex=totalLength/2;
            rightIndex=totalLength/2;
        }else{
            leftIndex=totalLength/2-1;
            rightIndex=totalLength/2;
        }
        int num1Counter=0;
        int num2Counter=0;
        double leftNum=0;
        double rightNum=0;
       //第一个坑在这儿，totalCounter<rightIndex+1.因为index是从0开始数多，我们这里需要的是循环的次数，所以要加1
        for(int totalCounter=0;totalCounter<rightIndex+1;totalCounter++){
            double num1=0;
            double num2=0;
            //第二个坑在这儿，如果其中一个数组被遍历完了这个时候应该怎么办（我的解决方案就是往后面塞正无穷）
            if(num1Counter>nums1.length-1){
                num1=POSITIVE_INFINITY;
            }else{
                num1=nums1[num1Counter];
            }
            if(num2Counter>nums2.length-1){
                num2=POSITIVE_INFINITY;
            }else{
                num2=nums2[num2Counter];
            }
           if(totalCounter<leftIndex){
               if(num1<num2){
                   num1Counter++;
               }else{
                   num2Counter++;
               }
           }else if(totalCounter==leftIndex){
               if(num1<num2){
                   leftNum=num1;
                   num1Counter++;
               }else{
                   leftNum=num2;
                   num2Counter++;
               }
           }else{
               if(num1<num2){
                   rightNum=num1;
                   num1Counter++;
               }else{
                  rightNum=num2;
                   num2Counter++;
               }
           }
//第三个坑在这儿，如果想要统一写成ans=(leftNum+rightNum)/2是不行的，因为在leftindex和rightindex相等的时候
// 它最后根本不会到rightIndex这边，导致rightNum还是默认值
           if(totalLength%2==0) {
               ans = (leftNum + rightNum) / 2;
           }else{
               ans=leftNum;
           }
        }
        return ans;
    }