https://leetcode.com/problems/maximum-gap/description/
Problem:
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
题目大意:
给你一个没有排序的正整数数组。输出排序后，相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。
Example:
Input: [5, 0, 4, 2, 12, 10]
Output: 5
Explanation:
Sorted: [0, 2, 4, 5, 10, 12]
max gap is 10 – 5 = 5
Idea:
Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.
桶排序。用n个桶来存放数字。对于每个桶，只跟踪存储最大值和最小值。
max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.
max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶（如果有）必须为空。
max gap = b[j].min – b[i].min
Time complexity: O(n)
时间复杂度: O(n)
Space complexity: O(n)
空间复杂度: O(n)
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua // Runtime: 6 ms class Solution { public: int maximumGap(vector<int>& nums) { const int n = nums.size(); if (n <= 1) return 0; const auto mm = minmax_element(nums.begin(), nums.end()); const int range = *mm.second - *mm.first; const int bin_size = range / n + 1; vector<int> min_vals(n, INT_MAX); vector<int> max_vals(n, INT_MIN); for (const int num : nums) { const int index = (num - *mm.first) / bin_size; min_vals[index] = min(min_vals[index], num); max_vals[index] = max(max_vals[index], num); } int max_gap = 0; int prev_max = max_vals[0]; for (int i = 1; i < n; ++i) { if (min_vals[i] != INT_MAX) { max_gap = max(max_gap, min_vals[i] - prev_max); prev_max = max_vals[i]; } } return max_gap; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment