[LeetCode] 164. Maximum Gap

轉自LeetCode

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

<Solution>
第一種解法，就是先 sort，然後歷遍找答案

code 如下

第二種解法，是利用到 bucket sort 的概念

想法如下

• 將數字分配到相對應的 bucket，並且記錄每個 bucket 裡面的最大最小值

• 最後只需要歷遍每個 bucket，記算 bucket[i+1].minValue - bucket[i].maxValue，來找到最大的 gap

• 這個解法的關鍵點在於 bucketSize = (maxNum - minNum) / (size - 1)，這個值會是 gap 的最小值

code 如下(參考資料)