【leetcode】164. 最大间距

题目内容

164. 最大间距

思路分析

本题仍然是一道排序题，题目的核心是对数字进行排序，排好序后就很简单了。而题目要求使用线性时空间复杂度，因此不能使用基于比较的排序方法。

解法参考资料

方法一：基数排序

基数排序资料

基数排序是一种非比较的排序方式，可以实现O(n)的时空复杂度排序。目前为止见过的另一种基于非比较的排序方式为计数排序（它适用于上下界间隔比较小的情况，不适用于本题）。

其主要思想是对数字进行逐位比较：

建立10个桶，对应某一位上的数字
查看各数的个位，将各数按个位放入对应的桶中，如123的个位数为3，就放入代表着个位数为3的桶中
依次收集各个桶中的数，形成新的数组
对新的数组查看各数的十位，循环上述过程，直到所有的位被比完。

方法二：基于桶的算法

思想：发现排序后两数间的间距应该不小于d = (max_value - min_value) / (n - 1),其中max_value和min_value为数组中的最大数和最小数，n为数组长度（证明见解法参考资料）。因此可以建立若干个大小为d的桶，然后遍历数组将对应区间的数字放入对应的桶中。这样最大间距应该产生于不同的两个桶中的数字，即产生于上一个桶的最大值和当前桶的最小值之差中。

感觉这个方法还是比较绕的，也不容易想到...

代码

# include<vector>
# include<iostream>
# include<algorithm>
# include<math.h>

using namespace std;

// 基数排序
// 时间复杂度O(n*(digit))，digit为最大的位数
// 空间复杂度O(n*10)
// 然而，其实O(nlogn)也并不大，当数据个数达到2^31次方时，其实也才O(31n)
class Solution1 {
public:
    void radix_sort(vector<int>& nums) {
        // 计算最大位数（由于题目说了是非负整数，所以才能这么算）
        int max_value = *max_element(nums.begin(), nums.end());
        int digit = 0;
        while (max_value != 0) {
            max_value = max_value / 10;
            ++digit;
        }

        // 由低位向高位遍历
        for (int i = 0; i < digit; ++i) {
            // 桶
            vector<vector<int>> buckets(10);
            // 将数字放入对应位数的桶中
            for (auto num : nums) {
                // 数字的当前位
                int current_position_num = int(num / pow(10, i)) % 10;
                buckets[current_position_num].push_back(num);
            }
            nums.clear();
            for (auto bucket : buckets) {
                nums.insert(nums.end(), bucket.begin(), bucket.end());
            }
        }
    }
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        
        if (n < 2) return 0;

        radix_sort(nums);
        
        int max_gap = 0;
        for (int i = 1; i < n; ++i) {
            max_gap = max(max_gap, nums[i]-nums[i - 1]);
        }

        return max_gap;
    }
};

// 基于桶的算法
// 时间复杂度O(n)，对数组遍历了好几次，应该是几n
// 空间复杂度O(n)，将n个数放入了不同的桶中
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        
        if (n < 2) return 0;

        // 求出nums的最大值和最小值
        int max_value = *max_element(nums.begin(), nums.end());
        int min_value = *min_element(nums.begin(), nums.end());

        // 求出桶大小和个数
        // 桶的大小应至少为1，否则算桶个数时将出现/0的操作
        int bucket_size = max(1, (max_value - min_value) / (n - 1));
        int bucket_num = (max_value - min_value) / bucket_size + 1;

        vector<vector<int>> buckets(bucket_num);

        // 将数字放入对应区间的桶
        for (auto num : nums) {
            buckets[(num - min_value) / bucket_size].push_back(num);
        }

        int max_gap = 0;

        // 求出上个桶的最大值与当前桶的最小值
        int last_bucket_max_value = *max_element(buckets[0].begin(), 
                buckets[0].end()); 
        int current_bucket_min_value;
        for (int i = 1; i < buckets.size(); ++i) {
            if (buckets[i].size() == 0) continue;
            current_bucket_min_value = *min_element(buckets[i].begin(), 
                buckets[i].end());
            max_gap = max(max_gap, 
                current_bucket_min_value - last_bucket_max_value);
            last_bucket_max_value = *max_element(buckets[i].begin(), 
                buckets[i].end());
        }

        return max_gap;
    }
};

int main() {
    Solution s;
    vector<int> input{ 1,4 };
    // s.radix_sort(input);
    cout << s.maximumGap(input) << endl;
}

收获

没有太多收获