LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정렬된 숫자 배열 nums1(길이m), nums2(길이n)
2. output: 두 숫자 배열 전체 집합의 중간값 리턴
3. 제한 시간 복잡도 = O(log m+n)
   • nums1.length == m
   • nums2.length == n
   • 0 <= m <= 1000
   • 0 <= n <= 1000
   • 1 <= m + n <= 2000
   • 106 <= nums1[i], nums2[i] <= 106

Idea

제한 시간 복잡도가 log(n)이므로 한번의 탐색으로 중간 값을 찾아야한다는 뜻이다.

즉, 정렬을 사용하지 않아야하기 때문에, 각 배열에 커서를 두고 중간값의 위치만큼 커서를 조정하고 그 값을 리턴하도록 하였다.

전체 길이가 짝수인 경우 중간 2값의 평균을 리턴해야 하기 때문에 바로 전 이동한 커서의 값을 저장하고 있어야한다.

Solution

1. 각 배열에 포인터를 두고 중간 값(위치) 찾기 ⭕

   전체 길이가 짝수인 경우를 위해 현재 값과 이전 값을 저장

   class Solution {
       fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
           var last = 0
           var prev = 0
           var idx1 = 0
           var idx2 = 0
           while ((nums1.size + nums2.size) / 2 > (idx1 + idx2) - 1) {
               prev = last
               last = if (idx1 >= nums1.size) {
                   nums2[idx2++]
               } else if (idx2 >= nums2.size) {
                   nums1[idx1++]
               } else {
                   if (nums1[idx1] < nums2[idx2])
                       nums1[idx1++]
                   else
                       nums2[idx2++]
               }
           }
           return if ((nums1.size + nums2.size) % 2 == 1)  last.toDouble() else (prev + last) / 2.0
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

Point