728x90
반응형
LeetCode-4
Median of Two Sorted Arrays : Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
note : The overall run time complexity should be O(log (m+n)).
Answer
:::python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
p = nums1 + nums2
p.sort()
if len(p)%2!=0:
median = p[len(p)//2]
else:
median = (p[len(p)//2]+p[len(p)//2-1])/2
return median
Result : 93ms Memory: 14mb
Median of Two Sorted Arrays
- 두 개의 정렬된 배열이 주어질 때, 두 배열의 중앙값을 찾는 문제입니다.
- 예를 들어, 배열 A = [1, 3, 5], 배열 B = [2, 4, 6] 이 주어지면, 중앙값은 (3+4)/2 = 3.5 가 됩니다.
- 두 배열의 크기는 같은 경우도 있지만, 다른 경우도 있으므로 코드로 구현할 때에는 이를 고려하여 작성해야 합니다.
- 이 문제는 이진 검색을 활용하여 풀 수 있습니다. 이진 검색이란 배열을 반으로 나누어 탐색하는 방법으로, 시간복잡도는 O(log(n+m)) 입니다.
- 이진 검색을 이용해 두 배열을 나누고, 각각의 중간값을 비교하여 조건에 따라 배열의 왼쪽 또는 오른쪽 부분만 탐색합니다.
- 마지막으로 중앙값을 찾아 반환합니다.
반응형
'One step' 카테고리의 다른 글
[leetcode-7] Reverse Integer (0) | 2023.04.16 |
---|---|
[leetcode-9] Palindrome Number (0) | 2023.04.15 |
[leetcode-3] Longest Substring Without Repeating Characters (0) | 2023.04.14 |
[leetcode-23] Merge k Sorted Lists (0) | 2023.04.09 |
[leetcode-641] Design Circular Deque (0) | 2023.04.08 |