4. Median of Two Sorted Arrays

문제 주소

https://leetcode.com/problems/median-of-two-sorted-arrays/

Median of Two Sorted Arrays - LeetCode

 

문제

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• 106 <= nums1[i], nums2[i] <= 106

문제 풀이

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        i = 0;
        j = 0;
        k = 0;
        nums=list()
        while(i<len(nums1)&j<len(nums2)):
            if(nums1[i]<nums2[j]):
                nums.insert(k,nums1[i])
                k=k+1
                i=i+1

            elif(nums1[i]>nums2[j]):
                nums.insert(k,nums2[j])
                k=k+1
                j=j+1

            elif(nums1[i]==nums2[j]):
                nums.insert(k,nums2[j])
                k=k+1
                j=j+1

                nums.insert(k,nums1[i])
                k=k+1
                i=i+1

        if(j<len(nums2)):
            while(j<len(nums2)):
                nums.insert(k,nums2[j])
                k=k+1
                j=j+1

        if(i<len(nums1)):
            while(i<len(nums1)):
                nums.insert(k,nums1[i])
                k=k+1
                i=i+1

        if(len(nums)%2==0):
            return (nums[int(len(nums)/2)]+nums[int(len(nums)/2)-1])/2
        else:
            return nums[int(len(nums)/2)]

결과

Case 1 F

Input

nums1 =

[1,3]

nums2 =

[2]

Output

1.00000

Expected

2.00000

Case 2 T

Input

nums1 =

[1,2]

nums2 =

[3,4]

Output

2.50000

Expected

2.50000

 

이때 저 while이 아예 안 돌아간다는 걸 모르고 헤맴

그 과정에서 insert , extend, append 세개 다 써봤다 

 

망한 extend 응용

나는 코드를 잘 짰다고 생각하는데 왜 안 되는지 몰라서 중간중간 뽑아보려고 vscode에서 돌려봄

# Definition for singly-linked list.
from ast import List
import math

class Main:
    nums1= [1,3]
    nums2 = [2]
    i = 0;
    j = 0;
    k = 0;
    nums=list()
    while(i<len(nums1)&j<len(nums2)):
        if(nums1[i]<nums2[j]):
            nums.extend(list(nums1[i]))
            k=k+1
            i=i+1
            print(nums)

        elif(nums1[i]>nums2[j]):
            nums.extend(list(nums2[j]))
            k=k+1
            j=j+1
            print(nums)

        elif(nums1[i]==nums2[j]):
            nums.extend(list(nums2[j]))
            k=k+1
            j=j+1

            nums.extend(list(nums1[i]))
            k=k+1
            i=i+1
            print(nums)

    if(j<len(nums2)):
        while(j<len(nums2)):
            nums.extend(list(nums2[j]))
            k=k+1
            j=j+1
            print(nums)

    if(i<len(nums1)):
        while(i<len(nums1)):
            nums.extend(list(nums1[i]))
            k=k+1
            i=i+1
            print(nums)

    if(len(nums)%2==0):
        print((nums[int(len(nums)/2)]+nums[int(len(nums)/2)-1])/2)
    else:
        print(nums[int(len(nums)/2)])

    
    
    

    def main():
        l=0
            

    if __name__ == "__main__":
        main()

 

TypeError: 'int' object is not iterable nums.extend(list(nums2[j]))

이게 떠서 list형식이어야 돌아가지나 하고 list생성자로 감싸면서 넣어보기까지 함 ㅋㅋ..

그러면 더더욱 이상해지는 건데요

알고보니 insert랑 append와 달리 extend는 원소를 넣어주는게 아니라 그냥 통채로 원소로 들어가는 거였다.

x = ['a','b','c']
y = ['d','e']
x.append(y)
print('x:' , x)

x: [’a’,’b’,’c’,[’d’,’e’]]

x = ['a','b','c']
y = ['d','e']
x.extend(y)
print('x:' , x)

x: [’a’,’b’,’c’,’d’,’e’]

 

x = ['a','b','c']
y = [['a','b']]
x.append(y)
print('x:' , x)

x: [’a’,’b’,’c’,[[’a’,’b’]]]

x = ['a','b','c']
y = [['a','b']]
x.extend(y)
print('x:' , x)

x: [’a’,’b’,’c’,[’a’,’b’]]

 

여태까지 list 안에 list를 또 넣고 있었던 것.... 충격과 공포.....

 

append로 바꿈

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        i = 0;
        j = 0;
        nums=list()
        while(i<len(nums1)&j<len(nums2)):
            if(nums1[i]<nums2[j]):
                nums.append(nums1[i])
                i=i+1

            elif(nums1[i]>nums2[j]):
                nums.append(nums2[j])
                j=j+1

            elif(nums1[i]==nums2[j]):
                nums.append(nums2[j])
                j=j+1

                nums.append(nums1[i])
                i=i+1

        if(j<len(nums2)):
            while(j<len(nums2)):
                nums.append(nums2[j])
                j=j+1

        if(i<len(nums1)):
            while(i<len(nums1)):
                nums.append(nums1[i])
                i=i+1

        if(len(nums)%2==0):
            return (nums[int(len(nums)/2)]+nums[int(len(nums)/2)-1])/2
        else:
            return nums[int(len(nums)/2)]

Input

nums1 =

[1,3]

nums2 =

[2]

Output

1.00000

Expected

2.00000

 

또 1나옴

내 코드는 의심할 여지가 없이 논리적으로 멀쩡한데 자꾸 결과가 이상하게 나와서 어이없었다

좀 살펴보다 보니 while문이 아예 안 돌아가고 밑으로 넘어가서 차례로 넣는다는게 밝혀졌다 

 

while 문이 돌아가지 않았던 이유는 괄호를 안 쳐서 먼저 되는 연산이 이상한게 되었기 때문이다

연산자의 우선순위가 기억이 나지 않아서 그냥 대충 true & true로 될 것 같아 이렇게 해놨더니 &를 가장 먼저 연산해버린 듯 하다

 

while(i<len(nums1)&j<len(nums2)):

 

& 좌우를 괄호로 묶어줬더니 됐다

while((i<len(nums1))&(j<len(nums2))):

 

최종 답안

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        i = 0;
        j = 0;
        nums=list()
        while((i<len(nums1))&(j<len(nums2))):
            if(nums1[i]<nums2[j]):
                nums.append(nums1[i])
                i=i+1

            elif(nums1[i]>nums2[j]):
                nums.append(nums2[j])
                j=j+1

            elif(nums1[i]==nums2[j]):
                nums.append(nums2[j])
                j=j+1

                nums.append(nums1[i])
                i=i+1

        if(j<len(nums2)):
            while(j<len(nums2)):
                nums.append(nums2[j])
                j=j+1

        if(i<len(nums1)):
            while(i<len(nums1)):
                nums.append(nums1[i])
                i=i+1

        if(len(nums)%2==0):
            return (nums[int(len(nums)/2)]+nums[int(len(nums)/2)-1])/2
        else:
            return nums[int(len(nums)/2)]