[88] Merge Sorted Array

給兩個sorted array,
要把第二個merge進第一個,
讓第一個變成兩個組起來的sorted array.
可假定第一個array有足夠空間把第二個存進去.

寫完第一版, 看執行時間並不快,
想說難道是要把第二個先全部接到第一個的尾端,
然後再把新array丟去sort, 這樣會比較快嗎?!
明明我就看到兩個for XD 我還只有一個耶 ！

後來發現LeetCoce上面寫的時間只能參考,
我copy執行 0ms的下來跑, 結果跑的比我的還慢啊= =
原來一切都是幻覺 QQ
那我就貼我的版本就好了cc
不用refine了反正我沒有天份～（奔入雨中)

Merge Sorted Array
void merge(int* nums1, int m, int* nums2, int n) {
    if (n==0)
        return;
     
    int i=m-1;
    int j=n-1;
    while(i>=0 && j>=0)
    {
        if(nums1[i] < nums2[j])
            nums1[i+j+1] = nums2[j--];
        else
            nums1[i+j+1] = nums1[i--];
    }
    if (i<0)
    {
        for(int q=0;q<=j;q++)
            nums1[q]=nums2[q];
        return;      
    }
    if (j<0)  //可以直接回傳了, 這段其實可以拿掉
    {
        return;
    }
}

[20250930更新]

嗯....所以我當年在寫什麼啊哈哈哈XD 看起來是一個當年比現在聰明的fu Orz

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {

int *idxs = calloc (m+n, sizeof (int));

int idx =0;

int i=0, j=0;

while (idx<(m+n) && i<m && j<n)

{

if (nums1[i]< nums2[j])

{

idxs[idx++]= nums1[i];

i++;

}

else

{

idxs[idx++]=nums2[j];

j++;

}

}

while (i<m)

idxs[idx++]= nums1[i++];

while (j<n)

idxs[idx++]= nums2[j++];

memcpy (nums1, idxs, sizeof (int) *(m+n));

return;

}

明天再來寫一次.

(隔日)結果只能寫這樣。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {

int i=m-1;

int j=n-1;

int idx = m+n-1;

while (idx>=0)

{

//printf("%d %d %d \n", idx, i,j);

if (i<0)

nums1[idx--]=nums2[j--];

else if (j<0)

nums1[idx--]=nums1[i--];

else if (nums1[i]> nums2[j])

nums1[idx--] = nums1[i--];

else

nums1[idx--] = nums2[j--];

}

return;

}

但看看別人，其實while 只需要看nums2的長度。當它跑完，如果nums1 還有剩，它會留在原地自動排好(?)

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {

int i=m-1;

int j=n-1;

int idx = m+n-1;

while (j>=0)

{

if (i>=0 && nums1[i]> nums2[j])

nums1[idx--] = nums1[i--];

else

nums1[idx--] = nums2[j--];

}

return;

}