[leetcode] (Array101) 88. Merge Sorted Array

 

You are given two integer arrays nums1 and nums2, sorted in non-decreasing 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.

 

Answers

mine

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        List mergeList = new ArrayList();

        for (int num : nums1) mergeList.add(num);
        for (int num : nums2) mergeList.add(num);
        
        while(mergeList.remove(Integer.valueOf(0))) { }

        Collections.sort(mergeList);

        for (int i=0; i < m+n; i++) {
            nums1[i] = (int) mergeList.get(i);
        }

        // for (int i=0; i < mergeList.size(); i++) {
        //     System.out.print(mergeList.get(i)); // 122356
        // }
    }
}

 

아래 예제에서 통과하지 못하고 실패했다. 0은 다 삭제하도록 했었는데 m의 자리까지 있는 0은 살려뒀어야 함...

 

leetcode 풀이법에서 모두 투 포인터 솔루션을 쓰고 있길래 일단 two pointer 방법부터 공부했다.

배열 하나에 포인터를 두 개 두고 위치를 바꿔치기하는 방법을 투 포인터라고 하는 것 같다.

 

투 포인터 해결방법

https://leetcode.com/problems/merge-sorted-array/solutions/3436053/beats-100-best-c-java-python-and-javascript-solution-two-pointer-stl

 

포인터 두 개 i와 j를 사용한다.

i의 초기값은 nums1의 유효한 값들 중 마지막 인덱스를 가르키고 ( ex: 2 3 4 0 0 0 일경우 m=3이고 i의 값은 2다.)

j의 초기값은 nums2의 유효한 값들 중 마지막 인덱스를 가르킨다. ( ex: 3 4 1 일경우 n=3이고 j의 값은 2다.)

k는 nums1의 마지막 인덱스다. 맨 끝에 가장 큰 값을 담아두기 위해 사용한다.

i와 j를 비교한 뒤 k의 위치에 담아두는 것이 포인트다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }

 

nums1의 값이 nums2의 값보다 클 경우 >>> k에 i인덱스 값을 넣어둔 뒤 --처리.

---

       

* ArrayList에서 특정값 없애기 * https://hianna.tistory.com/564

mergeList.remove(0); // 0번 인덱스가 삭제됨
mergeList.remove(Integer.valueOf(0)); // 첫번째 0 한개만 삭제됨
while(mergeList.remove(Integer.valueOf(0))) { } // 삭제할 것이 없으면 false를 반환하므로

 

 

* ArrayList.get(int index) // 인덱스에 위치한 객체를 리턴 * 

String[] fruitsArray = {"apple", "banana", "kiwi", "mango"};
ArrayList<String> fruits = new ArrayList<>(Arrays.asList(fruitsArray));
System.out.println(fruits.get(0)); // apple
System.out.println(fruits.get(2)); // kiwi
fruits.get(4); // IndexOutOfBoundException

 

* list.add() * https://blog.naver.com/mdown/221873603331

ArrayList list = new ArrayList();
list.add("hello");
list.add(new Integer(10)); // list.add(Object o)
list.add(10); // 그러나 java 5.0의 AutoBoxing으로 가능해짐
list.add(0, "bye"); // (index, 값)

// 출력
for (int i =0; i < list.size(); i++) {
	Object o = list.get(i); // get으로 가져온 데이터는 Ojbect형이다.
	System.out.println(o.toString());
}

// 또는
for (Object object : list) {
	System.out.println(object.toString());
}

 

* Object to int * https://dkswnkk.tistory.com/528

int i = (Integer) object;
int i = (int) object; // java 7.0
int i = Integer.parseInt((String.valueOf(Object)));
int i = Integer.parseInt((String) Object);

 

* 증감연산자 i--, --i *

int i = 0;
System.out.println(i++); // 0
System.out.println(i); // 1

 

증감연산자가 변수 뒤에 붙을 경우, 코드 행이 실행된 뒤에 연산이 진행된다. (i++문장이 실행된 뒤에 i값이 증가한다.)

int j = 0;
System.out.println(++j); // 1
System.out.println(j); // 1

++i의 경우에는 i값이 먼저 증가되고 나서, 코드 행이 실행된다.