首页 > itarticle > 4. median of two sorted arrays

4. median of two sorted arrays

admin 1月 30, 2021 0

Description

Difficulty: Hard

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)).

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

The median is 2.0

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

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

给出两个有序数列，返回两个数列形成的大数列的中位数。

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
67
68
69
 
class (object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        p1 = 0
        p2 = 0
        
        isOdd = True
        
        # last nums
        last = 0
        
        if (len(nums1) + len (nums2)) % 2 == 1:
            exp_num = (len(nums1) + len (nums2) + 1) / 2
            isOdd = True
        else:
            exp_num = ((len(nums1) + len (nums2)) / 2) + 1
            isOdd = False
            
        if len(nums1) == 0 or len(nums2) == 0:
            comb = nums1 + nums2
            if isOdd == True:
                return comb[exp_num - 1]
            else:
                return (comb[exp_num - 1] + comb[exp_num - 2]) / float(2)
        elif nums1[-1] <= nums2[0]:
            comb = nums1 + nums2
            if isOdd == True:
                return comb[exp_num - 1]
            else:
                return (comb[exp_num - 1] + comb[exp_num - 2]) / float(2)
        elif nums2[-1] <= nums1[0]:
            comb = nums2 + nums1
            if isOdd == True:
                print(comb[exp_num])
                return comb[exp_num - 1]
            else:
                return (comb[exp_num - 1] + comb[exp_num - 2]) / float(2)
        while p1 + p2 <= exp_num - 2:
            if p1 >= len(nums1):
                last = nums2[p2]
                p2 += 1
            elif p2 >= len(nums2):
                last = nums1[p1]
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                last = nums1[p1]
                p1 += 1
            else:
                last = nums2[p2]
                p2 += 1
        
        if p1 >= len(nums1):
            toAdd = nums2[p2]
        elif p2 >= len(nums2):
            toAdd = nums1[p1]
        else:
            toAdd = min(nums1[p1], nums2[p2])
        
        if isOdd == True:
            return toAdd
        else:
            return (toAdd + last) / float(2)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能