[c/LeetCode] Median of Two Sorted Arrays

1. 첫 번째 아이디어

일단 아무 생각 없이 배열 동적할당 해서 무지성으로 값을 넣은 다음에 정렬해서 중앙값을 구하자고 생각했음.

근데 돌아가긴 하는데, 애초에 정렬을 버블 정렬을 썼더니 (m+n)^2이 나와서 시간이

85ms / 6.9MB 라는 엄청나게 쓰레기 같은 성능의 코드를 작성해버렸음... 무지성 코딩 멈춰

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int resultSize = nums1Size + nums2Size;
    int *resultList = malloc(sizeof(int) * resultSize);
    
    int index = 0;
    for(int i = 0;i < nums1Size;i++)
    {
        resultList[index] = nums1[i];
        index++;
    }
    for(int i = 0;i < nums2Size;i++)
    {
        resultList[index] = nums2[i];
        index++;
    }
    
    for(int i=0;i<resultSize;i++)
    {
        for(int j = i+1;j<resultSize;j++)
        {
            if (resultList[i] > resultList[j])
            {
                int temp = resultList[i];
                resultList[i] = resultList[j];
                resultList[j] = temp;
            }
        }
    }
    double result = 0;
    if (resultSize % 2 == 0)
    {
        result = (resultList[resultSize/2] + resultList[resultSize/2 - 1]) / 2.0;
    }
    else
    {
        result = resultList[resultSize / 2];
    }
    return result;

}

 

 

2. 두 번째 아이디어

이에 충격받은 나머지 정렬하지 않고 배열에 넣을 때 부터 차례대로 넣어보자고 생각했음

결과는 17ms / 7MB

많이 줄이긴 했는데 여전히 10ms 이상이다.

더 생각해봐야겠다

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int resultSize = nums1Size + nums2Size;
    int index = 0, index1 = 0, index2 = 0;
    double result = 0;
    int *resultList = malloc(sizeof(int) * resultSize);
    
    while(index1 < nums1Size && index2 < nums2Size)
    {
        if (nums1[index1] <= nums2[index2])
        {
            resultList[index] = nums1[index1];
            index1++;
        }
        else if (nums1[index1] > nums2[index2])
        {
            resultList[index] = nums2[index2];
            index2++;
        }
        index++;
    }
    
    while (index1 < nums1Size)
    {
        resultList[index] = nums1[index1];
        index++;
        index1++;
    }
    while (index2 < nums2Size)
    {
        resultList[index] = nums2[index2];
        index++;
        index2++;
    }
    
    if (resultSize % 2 == 0)
    {
        result = (resultList[resultSize/2] + resultList[resultSize/2 - 1]) / 2.0;
    }
    else
    {
        result = resultList[resultSize / 2];
    }
    free(resultList);
    return result;

}