Leetcode164.最大间距（困难--快排、桶、基数排序）

题目描述：

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于2，则返回0。

示例1：

输入：[3, 6, 9, 1]
输出：3
解释：排序后的数组是[1, 3, 6, 9]，其中相邻元素(3, 6)和(6, 9)之间都存在最大差值3。

示例2：

输入：[10]
输出：0
解释：数组元素个数小于 2，因此返回 0。

说明:

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
`请尝试在线性时间复杂度和空间复杂度的条件下解决此问题`

解答思路1（快速排序）：

利用快速排序对数组中的元素进行排序，再遍历元素比较元素间的间距，取得最大间距。
快速排序是一种最坏情况时间复杂度为Θ(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它还能够进行原址排序，甚至在虚拟环境中也能很好地工作。
快速排序的运行时间依赖于划分是否平衡，而平衡与否又依赖于划分的元素。如果划分是平衡的，那么快速排序算法性能与归并排序一样。如果划分不平衡，那么快速排序的性能就接近于插入排序了。
快速排序的平均运行时间更接近于其最好情况，只要划分是常数比例的，算法的运行时间总是O(nlgn)。

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0
        
        def QuickSort(nums, l, r):
            if l < r:
                m = Partition(nums, l, r) # 算法的关键部分，实现对子数组的原址重排
                QuickSort(nums, l, m-1)
                QuickSort(nums, m+1, r)
        
        def Partition(nums, l, r):
            target = nums[r]
            i = l - 1
            while l < r:
                if nums[l] < target:
                    i += 1
                    nums[i], nums[l] = nums[l], nums[i]
                l += 1
            nums[i+1], nums[r] = nums[r], nums[i+1]
            return i+1
        
        QuickSort(nums, 0, len(nums)-1)
        
        i = 0
        j = 1
        maxi = float('-inf')
        while j < len(nums):
            if nums[j] - nums[i] > maxi:
                maxi = nums[j] - nums[i]
            i += 1
            j += 1
        return maxi

存在问题：

不满足题目说明中以线性时间复杂度的要求。

解答思路2（桶）：

对整个数组排序的代价很大，最坏情况下需要让每个元素都和其他所有元素比较。
如果我们不需要比较所有元素对呢？如果我们将元素分类，比如说用桶，这个想法将是可能的。我们只需要比较这些桶即可。

"""
代码来自LeetCode用户gymer
"""
class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 桶排序
        # 参考：https://blog.csdn.net/zxzxzx0119/article/details/82889998
        # 设置n+1个桶是为了保证间距最大的两个数被分到不同的桶中
        # 因为最大间距 x >= (max_val - min_val) / (n-1)
        # 而使用n+1个桶每个桶中数的差值最大为 (max_val - min_val) / n 因此一个桶不可能同时存放间距最大的两个数
        if len(nums) < 2:
            return 0
        min_val, max_val, n = float('inf'), float('-inf'), len(nums)
        for i in range(n):
            if nums[i] < min_val:
                min_val = nums[i]
            if nums[i] > max_val:
                max_val = nums[i]

        if min_val == max_val:
            return 0

        mins = [0] * (n + 1)
        maxs = [0] * (n + 1)
        has_num = [False] * (n + 1)

        for num in nums:
            index = int((num - min_val) * n / (max_val - min_val))
            mins[index] = num if not has_num[index] else min(mins[index], num)
            maxs[index] = num if not has_num[index] else max(maxs[index], num)
            has_num[index] = True

        max_len = 0
        m = maxs[0]
        for i in range(1, n + 1):
            if has_num[i]:
                curr_len = mins[i] - m
                if curr_len > max_len:
                    max_len = curr_len
                m = maxs[i]

        return max_len

解答思路3（基数排序）：

基数排序是一种非比较型整数排序算法，其原理是将数据按位切割成不同的数字，然后按每个位数分别比较。
引理8.3(算法导论) 给定n个d位数，其中每一个数位有k个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时Θ(n+k)，那么它就可以在Θ(d(n+k))时间内将这些数排好序。
基数排序可以看成桶排序的扩展，也是用桶来辅助排序。

import math

class Solution:
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return 0
        maxNum = nums[0]
        for i in range(1, len(nums)):
            if nums[i] >  maxNum:
                 maxNum = nums[i]
        location = 1  # 当前排序位置
        Sequence = [[] for _ in range(10)]  # 构造桶列表，分别存储单个位数0-9的数据

        while True:
            dd = math.pow(10, location-1)
            if  maxNum < dd:  # 判断是否已将数据排完
                break
            # 数据入桶
            for i in range(len(nums)):
                number = int(nums[i] / dd) % 10  # 计算数据在当前排序位置的余数，放入相应桶
                Sequence[number].append(nums[i])

            # 写回数组
            mm = 0
            for j in range(10):
                size = len(Sequence[j])
                for k in range(size):
                    nums[mm] = Sequence[j][k]
                    mm += 1
                Sequence[j].clear()
            location += 1
        maxGap = 0
        for i in range(1, len(nums)):
            maxGap = max(maxGap, nums[i] - nums[i-1])
        return maxGap