learningnote/MedianofTwoSortedArrays.py at master · JayFu/learningnote · 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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# -*- coding: utf-8 -*-

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

# nums1 = [1, 3]
# nums2 = [2]
# The median is 2.0

# nums1 = [1, 2]
# nums2 = [3, 4]
# The median is (2 + 3)/2 = 2.5

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)

        outputnums = []
        num2 = 0

        if (m + n) % 2 == 0:
            num2 = (m + n) // 2
            num1 = num2 - 1
        else:
            num1 = (m + n) // 2

        a = 0
        b = 0

        for i in range(0 , ((m + n) // 2 + 1)):
            if a >= m:
                outputnums.append(nums2[b])
                b += 1
            elif b >= n:
                outputnums.append(nums1[a])
                a += 1
            elif nums1[a] > nums2[b]:
                outputnums.append(nums2[b])
                b += 1
            else:
                outputnums.append(nums1[a])
                a += 1

        if num2 == 0: return outputnums[num1]
        else : return (float(outputnums[num1] + outputnums[num2])) / 2

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

# nums1 = [1]
# nums2 = [2,3,4,5,6]

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


# m = len(nums1)
# n = len(nums2)

# outputnums = []
# num2 = 0

# if (m + n) % 2 == 0:
#     num2 = (m + n) // 2
#     num1 = num2 - 1
# else:
#     num1 = (m + n) // 2

# a = 0
# b = 0

# for i in range(0, ((m + n ) // 2 + 1)):
#     if a >= m:
#         outputnums.append(nums2[b])
#         b += 1
#         # continue
#     elif b >= n:
#         outputnums.append(nums1[a])
#         a += 1
#         # continue
#     elif nums1[a] > nums2[b]:
#         outputnums.append(nums2[b])
#         b += 1
#     else:
#         outputnums.append(nums1[a])
#         a += 1
#     print(a , b)

# if num2 == 0: print(outputnums[num1])
# #python3解法：
# # else: print((outputnums[num1] + outputnums[num2]) / 2)
# #python2解法：
# else: print((float(outputnums[num1]) + float(outputnums[num2])) / 2)