Reading

排序算法

Feb 25, 2026
614 views
Algorithm
#Algorithm

164. 最大间距

题目

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

题解

如果进行排序，这里会超时。采用桶排序基础排序算法的思想，可以在线性时间解决。

  1. 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。
  2. 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。
\[每个桶的长度=\max(1,\lfloor{{\max(nums)-\min(nums)}\over{len(nums)-1}}\rfloor)\tag{1}\]
  1. 确定桶的数量，最后的加一保证了数组的最大值也能分到一个桶。为什么需要这样规定桶的尺寸呢？因为这样可以让最大的间距的两个元素在两个不同的桶中。可以证明一下，因为我们用元素范围之差除以元素个数，所以桶的尺寸就是平均的元素间距，显然最大间距的两个元素不可能在同一个桶。为什么要最大间距的元素在两个不同的桶中呢？如果两个元素在桶中，那就又需要再桶中进行排序求解了，这样桶排序的优势就没了。
\[桶的数量=\lfloor{{\max(nums)-\min(nums)}\over{每个桶的长度}}\rfloor+1\tag{2}\]
  1. 遍历数组，把元素放到桶中。这里只需要一个桶中元素的最大值和最小值，因为答案不会在一个桶中，所以，只需要比较相邻桶的边界就能获取答案，其余的值只会碍事。
  2. 遍历桶，用当前桶的最小值减去上一个桶的最大值，就是可能的答案。

举个例子

text
nums = [1,3,4,5,6,10,11,12,17]
每个桶的长度 = （17 - 1） / (9-1) = 2
桶的个数 = （17-1）/ 2 + 1 = 9
所以我们的桶为（左闭右开）：
| 区间 | [1,3) | [3,5) | [5,7) | [7,9) | [9,11) | [11,13) | [13,15) | [15,17) | [17,19) |
|------|-------|-------|-------|-------|--------|---------|---------|---------|---------|
| 元素 | 1     | 3,4   | 5,6   |       | 10     | 11,12   |         |         | 17      |

| 差值 | 3-1 = 2 | 5-4 = 1 | 10-6 = 4 | 11-10 = 1 | 17-12 = 5 |
|------|-------|-------|-------|-------|--------|
答案 = max（差值） = 5

代码

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0

        # 一些初始化
        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0

        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]

        # 把数字放入桶中
        for i in range(len(nums)):
            loc = (nums[i] - min_) // each_bucket_len
            buckets[loc].append(nums[i])

        # 遍历桶更新答案
        prev_max = float('inf')
        for i in range(len(buckets)):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i])-prev_max)

            if buckets[i]:
                prev_max = max(buckets[i])

        return max_gap

215. 数组中的第K个最大元素

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

题解

使用快排的思想

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        k = n - k
        l, r = 0, n-1
        while l <= r:
            p = self.partition(nums, l, r)
            if p < k:
                l = p + 1
            elif p > k:
                r = p - 1
            else:
                return nums[p]

    def partition(self, nums, left, right):
        pivot = nums[left]
        l, r = left+1, right
        while l <= r:
            while l <= r and nums[l] < pivot:
                l += 1
            while l <= r and nums[r] >= pivot:
                r -= 1
            if l > r:
                break
            nums[l], nums[r] = nums[r], nums[l]
        nums[left], nums[r] = nums[r], nums[left]
        return r