[Leetcode][Java] 88 Merge Sorted Array

[Leetcode][Java] 88 Merge Sorted Array

728x90

You are given two integer arrays nums1 and nums2, sorted in nondecreasing order,

and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function,

but instead be stored inside the array nums1.

To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged,

and the last n elements are set to 0 and should be ignored.

nums2 has a length of n.

두 개의 integer 오름차순 배열 nums1, nums2과 m, n integer를 받는다.

m, n은 각 배열이 가지고 있는 element의 개수이다.

이 두 배열을 하나의 오름차순 배열로 통합하여라.

단, 리턴되는 배열은 새로 정의된 배열이 아닌 nums1 배열이어야 한다.

nums1 배열은 크기가 m+n이다.

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

정렬된 두 개의 배열을 merge 해야 한다.

단, 새로운 배열을 생성하여 merge 하는 것이 아닌 주어진 배열에서 merge가 이루어져야 한다.

주어진 배열의 마지막 element들을 point 하고 그중에 큰 값을 nums1 배열에 입력하는 형식으로 문제를 해결해 보자.

해당 순회를 마무리하는 조건으로는 각 배열의 pointer들이 0보다 작아진 경우이다.

후에 만약 nums2의 pointer가 첫 index까지 순회를 하지 못한 경우에는 해당 값들을 nums1에 입력해주면 모든 배열을 순회한 것이다.

public void merge(int[] nums1, int m, int[] nums2, int n) { int nums1Idx = m - 1; int nums2Idx = n - 1; int point = nums1.length - 1; while (nums1Idx >= 0 && nums2Idx >= 0) { if (nums1[nums1Idx] >= nums2[nums2Idx]) { nums1[point] = nums1[nums1Idx]; point--; nums1Idx--; } else { nums1[point] = nums2[nums2Idx]; point--; nums2Idx--; } } if (nums2Idx >= 0) { while (nums2Idx >= 0) { nums1[point] = nums2[nums2Idx]; point--; nums2Idx--; } } }

시간 복잡도는 각 배열을 모두 순회하므로 O( M + N )이다.

문제 출처

https://leetcode.com/problems/merge-sorted-array/

728x90

from http://joomn11.tistory.com/93 by ccl(A) rewrite - 2021-12-10 20:28:17