[Leetcode] 88. Merge Sorted Array

Identifying the Problem

nums1과 nums2를 연결하고 오름차순 정렬한다.

Organizing thoughts

내 생각은 둘이 붙이고, bubble sort 하려 했는데

시간 복잡도 O(n+m) 인 방법도 있어서 다시 알아보았다.

 

Sourcecode (me)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int temp;
    
    
    for(int i=0;i<n;i++)
       *(nums1+m+i) = *(nums2+i);
    
    for(int i=0;i<nums1Size-1;i++)
    {
       for(int k=0;k<nums1Size-1-i;k++ )
           if(*(nums1+k) > *(nums1+k+1))
           { 
             temp = *(nums1+k);
             *(nums1+k) = *(nums1+k+1);
             *(nums1+k+1) = temp;

           }
     
    }
}

Sourcecode (other)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i=m-1, k=m+n-1, j=n-1; //i는 nums1의 마지막, j는 nums2의 마지막, k는 합배열의 마지막
    
    for (; k>=0 && i>=0 && j>=0;k--) //i,j,k가 모두 양수일 때만 반복, 
    								  
    {
        if (nums1[i] > nums2[j]) //nums1의 끝이 nums2 끝 보다 크면
        {
            nums1[k] = nums1[i]; //합배열의 끝을 nums1로 대입
            i--; //nums1 끝 index 앞쪽으로 (끝으로 보냈으니깐 볼일이 없지)
        }
        else //nums1의 끝이 nums2 끝 보다 같거나 작으면
        {
            nums1[k] = nums2[j]; //합배열의 끝을 nums1로 대입
            j--; 위와 마찬가지
        }
    }
    			// j가 먼저 음수가 돼 버리는 경우는 상관없지만,
    if (k >= 0) // nums1 [2,5,6] nums2 [1,2,3] 인 경우는 [2,2,2,3,5,6] 인 상태로 끝난다.
                // k가 0보다 크다는 말은 nums2가 정리가 안되었다는 말과 같다. 
    {
        for(;j>=0 && k>=0;j--,k--) //따라서 남은 k만큼 j를 정리해준다.
            nums1[k] = nums2[j];
    }
}

New things learned

하나의 배열안에 여러 가지 파라미터를 만들면 

시간 복잡도를 확연하게 줄일 수 있다는 사실을 알지만, 

내가 직접 생각하는 것은 쉽지 않은 것 같다.