[LeetCode]Maximum Gap

直接sort的话我们可以得到O(n * log n)的解法，但是题目要求我们给出O(n)的解法。那么基于比较的sort方法我们肯定不能用了，因为下界是O(n * log n)。我们就得考虑counting sort或者bucket sort之类O(n)的解法。首先我们可以想到Radix sort，radix sort是对每一位用counting sort来排序，之后得到所有数的排序。从低位到高位，从高到低都可以，假设最大的数有d为，总共n个数，那么排序的时间复杂度是O(d * n)。空间复杂度O(n + d)，代码如下：



Bucket sort我们也可以考虑，但是显然我们不能简单地将bucket size设为1，因为假设最大数和最小数相差很多的时候，是很费空间并且不效率的。具体我们可以参考这篇文章，简单来说，假设一组数量为n的数中最大数为max，最小数为min，那么maximum gap的最小值就为g = (max - min) / (n - 1)。因为假设所有数为等差数列，那么每个数的差就正好为g，那么任意移动任意一数，将其增加或者减小，就只会增加maximum gap的值。所以我们就将bucket size设为g，那么我们就有(max - min) / g + 1 = n个bucket，鉴于maximum gap的值永远>= g，我们只需要比较每一个bucket的最大值和下一个bucket的最小值即可。时间复杂度O(n)，空间复杂度O(n)，代码如下：