@@ -0,0 +1,1936 @@
+'''%0AGiven an unsorted array, find the maximum difference between the successive elements in its sorted form.%0A%0ATry to solve it in linear time/space.%0A%0AReturn 0 if the array contains less than 2 elements.%0A%0AYou may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.%0A%0A'''%0A%0Aclass Solution:%0A    # @param num, a list of integer%0A    # @return an integer%0A    def maximumGap(self, num):%0A        n = len(num)%0A        if n%3C2: return 0%0A        maxnum = num%5B0%5D; minnum = num%5B0%5D%0A        for i in xrange(n):%0A            minnum = min(num%5Bi%5D,minnum)%0A            maxnum = max(num%5Bi%5D,maxnum)%0A        %0A        bucket_size = (maxnum-minnum-1)/(n-1)+1%0A        bucket_min_max = %5B(float('inf'), float('-inf')) for i in xrange(n)%5D%0A        %0A        for i in xrange(n):%0A            index = (num%5Bi%5D-minnum)/bucket_size%0A            bucket_min_max%5Bindex%5D=(min(bucket_min_max%5Bindex%5D%5B0%5D,num%5Bi%5D),max(bucket_min_max%5Bindex%5D%5B1%5D,num%5Bi%5D))%0A        %0A        gap = 0%0A        premax = bucket_min_max%5B0%5D%5B1%5D%0A        for bucket_min, bucket_max in bucket_min_max%5B1:%5D:%0A            if bucket_min == float('inf'):%0A                continue %0A            gap = max(bucket_min - premax, gap)%0A            premax = bucket_max%0A            %0A        return gap%0A        %0A# test case: %5B1,1000000%5D, %0A# Reference: https://leetcode.com/discuss/18499/bucket-sort-java-solution-with-explanation-o-time-and-space%0A# %E8%BF%99%E9%81%93%E9%A2%98%E7%9B%AE%E7%9A%84%E6%80%9D%E8%B7%AF%E6%98%AF%EF%BC%9A%E5%AF%B9%E4%BA%8E%E7%BB%99%E5%AE%9A%E7%9A%84%E5%8C%BA%E9%97%B4%5Bimin, imax%5D,the max gap between the numbers should not smaller than ceiling%5B(imax-imin)/(n-1)%5D%0A# for example: %5B1,2,3,4,5,6,7,8,9%5D, %E5%A6%82%E6%9E%9C%E7%BB%99%E5%AE%9A%E7%9A%84%E4%B8%AA%E6%95%B0%E4%B8%BA3%EF%BC%8C%E5%8C%BA%E9%97%B4%E4%B8%BA1%E5%88%B09%EF%BC%8C%E6%9C%80%E5%B0%8F%E7%9A%84gap%E4%B8%BA4%EF%BC%8C%E4%BB%BB%E6%84%8F%E5%8F%963%E4%B8%AA%E6%95%B0%EF%BC%8C%E4%BC%9A%E5%8F%91%E7%8E%B0%E6%9C%80%E5%B0%8Fgap%E8%82%AF%E5%AE%9A%E4%B8%BA4%0A# %E6%88%91%E4%BB%AC%E5%8F%96n%E4%B8%AAbucket%EF%BC%8C%E6%89%80%E4%BB%A5%E7%AC%ACkth bucket contains numbers in %5Bmin+(k-1)gap, min + k* gap%5D%0A# Basically we argue that the largest gap can not be smaller than (max-min)/(N-1), %0A# so if we make the buckets smaller than this number, any gaps within the same bucket is not the amount we are looking for, %0A# so we are safe to look only for the inter-bucket gaps.%0A

Create Maximum_Gap.py