[LeetCode] 004. Median of Two Sorted Arrays JAVA

Median of Two Sorted Arrays - LeetCode

---

📍문제

ENG

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

KOR

크기가 각각 m과 n인 두 개의 정렬된 배열 nums1과 nums2가 주어지면 두 개의 정렬된 배열의 중앙값을 반환해야 한다.
전체 실행 시간 복잡도는 O(log(m+n))여야 한다.

---

📍예시

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 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.

---

📍풀이 설명

• 길이를 변수에 담아서 사용하기 위해 선언해주었다.

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

   int n = nums1.length;
   int m = nums2.length;

}

• 새로운 배열을 만들어 주었다.
• 길이는 입력되는 두 배열의 길이를 더해 반으로 나누고 +1을 해주었다.

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
   ...

   int[] arr = new int[(m + n) / 2 + 1];

}

• 첫 번째 배열의 길이 비교를 위한 변수와 두 번째 배열의 길이 비교를 위한 변수를 각각 선언한 후 초기화 해주었다.
• 반복문을 돌며 숫자의 크기를 비교하여 새로운 배열에 넣어주었다.
• 조건문은 길이 비교를 위한 것인데, 두 배열의 길이가 다를 수도 있기 때문이다.
• 비교하여 더 작은 수를 새 배열에 넣어주었다.
• 두 배열이 정렬된 배열이기 때문에 가능했다.

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
   ...

   while (one + two < arr.length) {
      if (one == n) {
         arr[one + two] = nums2[two++];
      } else if (two == m) {
         arr[one + two] = nums1[one++];
      } else {
         arr[one + two] = nums1[one] < nums2[two] ?
            nums1[one++] : nums2[two++];
      }
   }
}

• 그리고 리턴 값을 계산해주었다.
• 아래 처럼 계산식을 적어주면, 두 배열의 합이 홀수 일 경우 같은 값을 더한 후 나눠주기 때문에 중간값을 찾을 수 있고 두 배열의 합이 짝수일 경우 각각의 중간값을 더해 나누어 주어 중간값을 찾을 수 있다.
• 2.0으로 나누어준 이유는 나누는 값이 double이게 하기 위해서다. 
• 만약 2로 나눈다면, 나누기 과정에서 소수점이 날아가고 그 결과 값이 double형태로 출력되기 때문이다.

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
   ...

   return (arr[(n + m) / 2] + arr[(n + m - 1) / 2]) / 2.0;
}

---

📍최종 풀이

public class MedianOfTwoSortedArrays {
   public static void main(String[] args) {
      int[] arr1 = {};
      int[] arr2 = {2,4};
      int[] num1 = {1,3,7};
      int[] num2 = {2,4,5};
      System.out.println(findMedianSortedArrays(arr1, arr2));
      System.out.println(findMedianSortedArrays(num1, num2)); 
   }
   public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

      int n = nums1.length;
      int m = nums2.length;

      int[] arr = new int[(m + n) / 2 + 1];

      int one = 0;
      int two = 0;

      while (one + two < arr.length) {
         if (one == n) {
            arr[one + two] = nums2[two++];
         } else if (two == m) {
            arr[one + two] = nums1[one++];
         } else {
            arr[one + two] = nums1[one] < nums2[two] ?
               nums1[one++] : nums2[two++];
         }
      }

      return (arr[(n + m) / 2] + arr[(n + m - 1) / 2]) / 2.0;
   }
}

---