[378] Kth Smallest Element in a Sorted Matrix

當妳迷惘的時候
就用qsort啊 (?)
只要qsort開下去
就算不知道病因, 病也好了一半
比看醫生還有效
江湖郎中Q術士如是說.

Kth Smallest Element in a Sorted Matrix
int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
    int i,size= matrixRowSize*matrixColSize;
    int *new = malloc(sizeof(int)*size);
    for (i=0;i<size;i++)
    {
        new[i] = matrix[i/matrixColSize][i%matrixColSize];
    //printf("new[%d]\n", new[i]);
    }
    qsort(new,size,sizeof(int),compare);
    return new[k-1];
}

只是想必題目少寫了 ： 不可以另外copy成新的array吧 XD
現在memory那麼大, 開給我用有什麼關係XD
於是就看到很多heap啦 , priority queue啦這些 C 沒有內建的東西
據說是要用binary search 這樣.
哎唷二維的sorted array  search起來感覺好麻煩歐
為什麼要用二維喇一維不好嗎? (妳意見也太多 XD)
就不貼別人的code了...

大意是說matrix[0][0]一定是最小值, matrix[n-1][n-1] 一定是最大值
相加除以二 （或是 small + (big-small)/2  , 但這不是一樣嗎XD
可是寫後者的人多多多的多, 大概是怕overflow吧我猜.....)
於是我們有了一個中間值mid
接下來每行掃過去,  i跟 j 都要逐個做, 因為可能下一行還有比較小的值
並且同一行可能只會有  n-x個人大於 mid
算是一個算左上角有多少人小於mid 的概念
算完看這個值有沒有大於 k (k是題目要找的第k小數目)
超過k的話表示k 在左半, 我們把big 改成 mid
反之則把small改成mid, 去找右半
雖然這樣, 下一輪還是要從i, j 等於0 開始從頭掃起
若是k 很大的話就是左上角的範圍越來越大
(感覺一直在做一樣的事好像很笨?!)
(就說用一維qsort很好嘛)
(好了我時間不多了(要去哪)既然有想過了我們就跳過這一題吧)
然後就可以找到第k小的數目了...The End XD