[리트코드] 4. Median of Two Sorted Arrays

풀이방법_1

1. nums1길이 + nums2길이 만큼의 크기를 가지는 배열 nums 생성

2. System.arraycopy() 을 사용하여 두 개의 배열을 nums에 복사해서 넣음

3. Arrays.sort() 사용하여 nums 오름차순 정렬

4. nums의 길이가 홀 수 일때 -> 배열의 중앙값 return / 짝 수 일때 -> 배열의 중앙값 2개의 평균을 return

 

코드_1

import java.util.Arrays;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        System.arraycopy(nums1, 0, nums, 0, nums1.length);
        System.arraycopy(nums2, 0, nums, nums1.length, nums2.length);
        
        Arrays.sort(nums);
        if(nums.length % 2 == 0){
            return (nums[nums.length / 2] + nums[(nums.length / 2) - 1]) / 2.0;
        } else return nums[nums.length / 2];
        
    }
}

 

실행 결과_1

---

 

풀이_1에서 이미 정렬되어 들어오는 배열을 조작 후 다시 정렬하는 것과 중앙값이 필요한 것인데 전체 값들을 새로운 배열에 다 넣는다는 점 때문에 더 좋은 풀이가 없을까 생각하여 다음과 같은 방법으로도 풀어봤다:)

 

---

풀이방법_2

1. nums1길이 + nums2길이 만큼의 크기를 가지는 배열 nums 생성

2. nums1, nums2의 가장 작은 값을 가리키는 p1, p2를 선언

3. p1, p2가 가리키는 값 중 작은 값을 nums에 순서대로 넣고 다음으로 작은 값을 가리키도록 움직임

4. 3의 과정을 nums의 중앙위치에 값을 넣을때까지 반복

 (이때 nums1, nums2 중 하나의 배열을 전부 다 넣었다면 나머지 배열의 값 중 넣지않은 값을 nums의 중앙위치에 값까지 이어붙혀 넣는다.)

5. nums의 길이가 홀 수 일때 -> 배열의 중앙값 return / 짝 수 일때 -> 배열의 중앙값 2개의 평균을 return

 

코드_2

import java.util.Arrays;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int[] nums = new int[nums1.length + nums2.length];
        
        int p1 = 0, p2 = 0;
        for(int i = 0; i <= (nums.length / 2); i++) {
            //두 개의 배열 중 하나의 배열을 다 넣었을 경우
            if(p1 == nums1.length){
                System.arraycopy(nums2, p2, nums, i, (nums.length / 2) - i + 1);
                break;
            }
            if(p2 == nums2.length) {
                System.arraycopy(nums1, p1, nums, i, (nums.length / 2) - i + 1);
                break;
            }
            
            //둘 중 작은 값을 넣어줌
            if(nums1[p1] > nums2[p2]){
                nums[i] = nums2[p2];
                p2++;
            } else {
                nums[i] = nums1[p1];
                p1++;
            }
        }
        
        //중앙값 return
        if(nums.length % 2 != 0) return nums[nums.length / 2];
        else return (nums[(nums.length / 2) - 1] + nums[nums.length / 2]) / 2.0;

    }
}

 

실행 결과_2

 

---

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

Median of Two Sorted Arrays - LeetCode