[LeetCode/알고리즘] median of two sorted arrays

median of two sorted arrays

입출력 예제

nums1 = [1, 2] 

nums2 = [3, 4]

return : 2.5

해결 방법

여기서 가장 중요한 문제는 nums1과 nums2의 병합이다. 병합정렬을 알고 있다면 충분히 쉽게 풀 수 있다고 생각한다.

nums1과 nums2에 대해 각각에 처음 위치를 두고 왼쪽과 오른쪽에서 작은 순부터 새로운 배열(nums3)에 값을 차례대로 집어넣고 다 집어 넣었으면 덜 집어 넣은 배열을 한번에 nums3에 집어 넣어서 병합 정렬을 하면 된다.

median은 중앙값을 의미한다. nums3가 짝수개일때는 중앙이 애매하기 때문에 중앙에 있는 왼쪽과 오른쪽의 평균값을 취하고 홀수 개일때는 가운데의 값을 반환하면 된다.

소스 코드

public class Solution {
	 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		 int i=0;
		 int j=0;
		 List<Integer> nums3=new ArrayList<>();
		
		 
		 while(i<nums1.length&&j<nums2.length) {
			 if(nums1[i]<nums2[j]) {
				 nums3.add(nums1[i]);
				 i++;
			 }
			 else {
				 nums3.add(nums2[j]);
				 j++;
			 }
		 }
		 
		 while(i<nums1.length) {
			 nums3.add(nums1[i]);
			 i++;
		 }
		 while(j<nums2.length) {
			 nums3.add(nums2[j]);
			 j++;
		 }
		 
		 if(nums3.size()%2==0) {
			 return (double)(nums3.get(nums3.size()/2)+nums3.get((nums3.size()/2-1)))/2;
		 }
		 else {
			 return nums3.get(nums3.size()/2);
		 }
	 }
}