[373] Find K Pairs with Smallest Sums （TBC）

結果寫不出來 囧
放棄 囧
用C寫的人真的那麼少嗎！！！
因為用C去寫heap感覺太花時間了
找好久找到一個不用implement heap的解法
想說先commit成功後看看有沒有其他比較漂亮的寫法
結果沒有XD!
一方面是送C的commit很少(吧)
另一方面用C寫heap真的是超級落落長啊啊啊啊啊～～～
先記下別人的寫法(沒有用heap的)
但其實也是用c++寫的, 還要翻譯XD！

給兩個已經排序好的array, 要回傳前k個相加最少的倆倆一組index
這真的很囉唆(而且還只是medium難度我哭!)
有可能有一樣大小的數字,
另外k 有可能大於最多可能的pair
總言之言總之
交叉來回比真是太麻煩了(抱怨again)
找到的不用heap的解法是, 用另外一個array去記錄nums1裡每個item 比對到了nums2的哪一個
在我的腦袋爆炸的同時LeetCode網站也爆炸了 XD
維修了兩個半小時XD
另外一定要記得init !要記得init ! 要記得init !
清空它們！！！
還有不要以為memset 就清空了, 妳可能傳了錯的值啊啊啊啊啊～～～～（奔入雨中）
最後雖然列了一個 TBC, 但我感覺我回來寫它的機率很低, 以上 Orz

Find K Pairs with Smallest Sums
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int** columnSizes, int* returnSize) {
    if(nums1 == NULL || nums2==NULL || nums2Size ==0 || nums1Size==0)
    {
        *returnSize = 0;
        return NULL;
    }

    int i,j;
    *returnSize = k;

    int **matrix = malloc(sizeof(int*)*(nums1Size * nums2Size));
    int **ret = malloc(sizeof(int*)*(*returnSize));
    *columnSizes = malloc(sizeof(int*)*(*returnSize));

    for (i=0;i<nums2Size;i++)
    {
        matrix[i] = malloc(sizeof(int)*nums1Size);
        for(j=0;j<nums1Size;j++)
        {
            matrix[i][j] = nums1[j]+nums2[i];
//printf("i %d j %d %d + %d = %d\n", i,j,nums1[i],nums2[j],matrix[i][j]);
        }
    }
 
    for (i=0;i<(*returnSize);i++)
    {
        (*columnSizes)[i]= 2;      
        ret[i] = malloc(sizeof(int*)*2);

    }
//////////////////////
    {
        int size = (k< nums1Size*nums2Size)? k:nums1Size*nums2Size;
        int selected = 0;
        int* index = malloc(sizeof(int)*(nums1Size));
        int minVal;
     
         *returnSize = size;
     
        for(i=0;i<nums1Size;i++)
            index[i]=0;

        for(int t=0;t<size;t++)
        {
            minVal = INT_MAX;
            for(int i=0; i<nums1Size; i++)
            {
                if(index[i]==nums2Size)
                    continue;

                if(nums1[i] + nums2[index[i]] < minVal)
                {
                    minVal = nums1[i] + nums2[index[i]];
                    ret[t][0] = nums1[i];
                    ret[t][1] = nums2[index[i]];
                    selected = i;
                }
                if(index[i]==0)
                    break;
            }
            index[selected]++;
        }
     
        return ret;
    }
/////////////////////
    return ret;
}