[Python]最大ギャップの問題

さいだいギャツプもんだい
問題の説明
最大ギャップ問題とは、n個の実数x 1,x 2,.,x n x_1, x_2,...,x_n x1​,x2​,...,xn,このn個の数の実軸上の隣接する2個の数の間の最大差を求める.任意の実数の下で整数関数をとるのに時間がかかるO(1)O(1)O(1)を仮定し,最大ギャップ問題の線形時間アルゴリズムを設計した.
問題を解く構想.
第一の方法
まずn個の数を小さいから大きいまで並べ替え,次いで隣接する2つの数の間の距離を順次計算する.この方法を用いて,最適ソート法の計算複雑度はO(n∗l o g n)O(n*logn)O(n∗logn)であり,線形時間複雑度を満たさない.しかし、この方法は実現が簡単です.
2つ目の方法:バケツのソート

配列の最大値maxを見つけます.valと最小値min_val.

各バケツの幅はsize=(max_val-min_val)/(n-1)で、合計n+1バケツで、最後のバケツは最大値を保存し、n個の数はn+1バケツに入れ、必ず空きバケツが存在し、最大ピッチは必ず同じバケツから来ない.

それぞれの数をそれぞれのバケツに入れ、nums[i]は(nums[i]-min_val)/size番目のバケツに入れ、バケツごとにそのバケツ内の最小値と最大値のみを格納し、フォーマットは[min,max]である.

空きバケツを排除した後、隣接する2つのバケツ内の数字の最大距離、すなわちi番目のバケツの最小値とi-1番目のバケツの最大値との差を求める.

Pythonプログラム

第1の方法のPythonプログラム:

nums = [2.3, 3.1, 7.5, 1.5, 6.3]

class Solution:
    def maxmargin(self, nums):
        if len(nums) < 2:
            return 0

        max_nums, min_nums = max(nums), min(nums)
        if max_nums == min_nums:
            return 0

        sorted_nums = sorted(nums)
        margin = []
        for i in range(len(sorted_nums)):
            mar = sorted_nums[i] - sorted_nums[i-1]
            margin.append(mar)

        return format(max(margin), '.1f')


s = Solution()
b = s.maxmargin(nums)
print(b)

出力:

3.2

Process finished with exit code 0

第2の方法のPythonプログラム

import math

class Solution:
    def maximumGap(self, nums):
        if len(nums) < 2:
            return 0
        max_val, min_val = max(nums), min(nums)
        if max_val == min_val:
            return 0
        n = len(nums)
        size = (max_val - min_val) / (n - 1)

        bucket = [[None, None] for _ in range(n + 1)]
        for num in nums:
            b = bucket[math.floor((num - min_val) // size)]
            b[0] = min(b[0], num) if b[0] else num
            b[1] = max(b[1], num) if b[1] else num
        bucket = [b for b in bucket if b[0] is not None]
        return max(bucket[i][0] - bucket[i - 1][1] for i in range(1, len(bucket)))


nums = [2.3, 3.1, 7.5, 1.5, 6.3]
s = Solution()
b = s.maximumGap(nums)
print(format(b, '.1f'))

出力:

3.2

Process finished with exit code 0

参照先:https://www.jianshu.com/p/dbb8056344ea