[164] Maximum Gap

紀念我開始寫LeetCode 以來
第一次一commit就過的感人時刻ToT
當然照例我又忽略了題意上的"Try to solve it in linear time/space."
明明那個才是重點Orz
但是不管啦不管啦不管啦～～～～（在地上打滾）

給一個沒有sort的array,
回傳它sort好以後兩兩相鄰的最大差值.

Maximum Gap
int compare(const void* a, const void* b){
    return (*(int*)a-*(int*)b );
}

int maximumGap(int* nums, int numsSize) {
    if(numsSize<2)
        return 0;
    int i;
    int maxDiff=0;
    qsort(nums,numsSize,sizeof(int),compare);
    for(i=1;i<numsSize;i++)
    {
        if (nums[i]-nums[i-1] > maxDiff)
            maxDiff = nums[i]-nums[i-1];
    }
    return maxDiff;
}
但聽說應該要用Bucket Sort或是Radix Sort XDDDD
明天醒來如果沒有挑戰hard的精神就來看看這個吧QQ
然後再順便看一下Pigeon hole principle  XD
(要看的東西是不是越積越多, 然後都沒有清掉啊啊啊啊啊～～～～～～）
(再度陷入鬼叫模式）

update:
看完以後用bucket sort的概念,
結果果然沒想懂, 完全弄反Orz
為什麼還是覺得好浪費生命啊啊啊啊啊啊～～～～～
先找出最大值跟最小值, 因為已知個數,
所以排序以後的倆倆差值  不會小於 gap = (max-min) /(size-1)
(據說就會講到Pigeon hole principle  Orz）
於是使用 size個bucket, 存 min. min + gap , min+gap*2 ....的屬於這個bucket的值
也就是說同個bucket內任兩個數的差值不會大於 gap
然後只要存這個bucket內的最大跟最小值
把bucket處裡完以後, 再從頭掃一次bucket,
看相鄰的最大值跟最小值差, 取最大的 （頭昏了Orz）
如果某個中間的bucket是空的, 把差值加上gap, 繼續看下一個 bucket;
或者是可以存上一次的有值bucket最大值 (昏again）
因為原本就設計bucket在 min和max中間,
所以可以確定第一個和最後一個bucket一定有至少一個item
而每個bucket如果只有一個item,它的最大值會等於最小值
(當然嘛, 自己跟自己, 最大最小都是自己)
結束..........(倒在地上口吐白沫ing )

int maximumGap(int* nums, int numsSize) {
    if(numsSize<2)
        return 0;
    else if (numsSize==2)
        return  abs(nums[1]-nums[0]);
    int i,max = 0;
    int min = nums[0];
    for (i==0;i< numsSize; i++)
    {
        if (nums[i]> max)
            max = nums[i];
        if(nums[i]<min)
            min = nums[i];
    }
    int gap = (max - min) / (numsSize -1) +1;
    int *minBucket = malloc(sizeof(int)*(numsSize));
    int *maxBucket = malloc(sizeof(int)*(numsSize));
    memset(minBucket, -1 , sizeof(int)*numsSize);
    memset(maxBucket, 0 , sizeof(int)*numsSize);
    for(i=0;i < numsSize; i++)
    {
        int index = (nums[i]-min)/gap;
        if(minBucket[index]== -1 || minBucket[index] > nums[i])
            minBucket[index] = nums[i];
        if(maxBucket[index]<nums[i])
            maxBucket[index]=nums[i];
    }

    int diff = 0;
    int base = maxBucket[0];
    for(i=1; i< numsSize;i++)
    {
        if(minBucket[i] < 0)
            continue;
       
        if((minBucket[i]-base) > diff)
            diff = minBucket[i]-base;
        base = maxBucket[i];
    }
    return diff;
}