問(wèn)題描述：
給定一個(gè)數(shù)組，求有序后相鄰兩個(gè)數(shù)的最大差值，要求時(shí)間復(fù)雜度為O(n)
并且不能用非基于比較的排序算法

解決思路
我們使用桶排序的思想，但是不對(duì)數(shù)組進(jìn)行排序操作
因?yàn)槲覀冎恍枰@取當(dāng)前數(shù)組元素所在桶的序號(hào)，并不是真實(shí)地將元素插入某個(gè)桶中

下面只是模擬的過(guò)程：

1. 數(shù)組 a 中有 n 個(gè)元素，則準(zhǔn)備 n+1 個(gè)桶，將數(shù)組的最小值放入 0 號(hào)桶，最大值放入 n 號(hào)桶
2. 將數(shù)組剩余的 n-2 個(gè)元素按順序均勻放入剩余的 n-1 個(gè)桶中（每個(gè)桶中的元素是有序的），則必有一個(gè)空桶，
   因此要求的最大差值一定不會(huì)來(lái)自同一個(gè)桶的相鄰元素之差
3. 最大差值一定是相鄰兩個(gè)桶的后一個(gè)桶中最小值與前一個(gè)桶中最大值之差，相鄰兩個(gè)桶中間可能會(huì)有空桶

max_differ_sorted.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2018-06-16 23:09:23

"""
給定一個(gè)數(shù)組，求排序之后相鄰兩個(gè)數(shù)的最大差值，要求時(shí)間復(fù)雜度為O(n)
并且不能用非基于比較的排序算法

解決思路
我們使用桶排序的思想，但是不對(duì)數(shù)組進(jìn)行排序操作
因?yàn)槲覀冎恍枰@取當(dāng)前數(shù)組元素所在桶的序號(hào)，并不是真實(shí)地將元素插入某個(gè)桶中
下面只是模擬的過(guò)程：
1.數(shù)組 a 中有 n 個(gè)元素，則準(zhǔn)備 n+1 個(gè)桶，將數(shù)組的最小值放入 0 號(hào)桶，最大值放入 n 號(hào)桶
2.將數(shù)組剩余的 n-2 個(gè)元素按順序均勻放入剩余的 n-1 個(gè)桶中，則必有一個(gè)空桶，
  因此要求的最大差值一定不會(huì)來(lái)自同一個(gè)桶的相鄰元素之差
3.最大差值一定是相鄰兩個(gè)桶的后一個(gè)桶中最小值與前一個(gè)桶中最大值之差，相鄰兩個(gè)桶中間可能會(huì)有空桶
"""

from util import Util
from sort import Sort

def max_differ_sorted(a):
    """
    時(shí)間復(fù)雜度：O(n)
    """
    n = len(a)
    if n < 2:
        return 0

    _max = max(a)   #獲取最大值
    _min = min(a)   #獲取最小值
    # print(_min)
    # print(_max)
    if _min == _max:    #如果最大值等于最小值，則a中所有的數(shù)相等
        return 0

    # 準(zhǔn)備三個(gè)長(zhǎng)度為n+1的列表
    # hasNum記錄每個(gè)桶中是否有數(shù)字
    # mins記錄每個(gè)桶中的最小值
    # maxs記錄每個(gè)桶中的最大值
    hasNum = [False] * (n+1)
    mins = [None] * (n+1)
    maxs = [None] * (n+1)
    id = 0
    for i in range(0, n):
        id = bucket(a[i], n, _min, _max)    # 獲得當(dāng)前元素屬于哪個(gè)桶
        mins[id] = min(a[i], mins[id]) if hasNum[id] else a[i]
        maxs[id] = max(a[i], maxs[id]) if hasNum[id] else a[i]
        hasNum[id] = True

    # max_differ等于后一個(gè)桶最小值與前一個(gè)桶最大值之差的最大值
    res = 0
    lastMax = maxs[0]
    for j in range(1, n+1):
        if hasNum[j]:
            res = max(res, mins[j] - lastMax)
            lastMax = maxs[j]

    return res
    pass

def max_differ_sorted_std(a):
    """
    最直接的方法，先排序，再求相鄰的最大差值
    時(shí)間復(fù)雜度：平均O(nlogn) > O(n)
    """
    n = len(a)
    if n < 2:
        return 0

    Sort.quick_sort(a)
    res = 0
    for i in range(n-1):
        res = max(res, a[i+1] - a[i])
        pass
    return res
    pass

def bucket(x, n, min, max):
    """
    x：待放入桶中的數(shù)
    n：數(shù)組的長(zhǎng)度
    min：數(shù)組元素最小值
    max：數(shù)組元素最大值
    """
    return (x - min) * n // (max - min)
    pass

def test():
    a = Util.gen_randint_list()

    max_differ = max_differ_sorted(a)
    print(a)
    max_differ_std = max_differ_sorted_std(a)
    print(a)

    print('test: ', end = '')
    print(max_differ)
    print('std:  ', end = '')
    print(max_differ_std)

    if max_differ_std == max_differ:
        print('true')
    else:
        print('false')
    pass

if __name__ == '__main__':
    for x in range(10):
        test()
        pass

util.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2018-06-11 22:58:30

import random

class Util(object):
    """
    工具類
    """
    def gen_randint_list(n = 5, min = 0, max = 10):
        """
        生成一個(gè)隨機(jī)int型列表
        """
        if n < 1 or min > max:
            return []

        rand_list = []
        for i in range(n):
            rand_list.append(random.randint(min, max))
            
        return rand_list
        pass

測(cè)試結(jié)果

max_differ_sorted.PNG