C++实现LeetCode(164.求最大间距)
[LeetCode] 164. Maximum Gap 求最大间距
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: [3,6,9,1]Example 2:
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.
Input: [10]Note:
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
- Try to solve it in linear time/space.
class Solution {public:int maximumGap(vector& nums) {if (nums.size() <= 1) return 0; int mx = INT_MIN, mn = INT_MAX, n = nums.size(), pre = 0, res = 0; for (int num : nums) {mx = max(mx, num); mn = min(mn, num); }int size = (mx - mn) / n + 1, cnt = (mx - mn) / size + 1; vector bucket_min(cnt, INT_MAX), bucket_max(cnt, INT_MIN); for (int num : nums) {int idx = (num - mn) / size; bucket_min[idx] = min(bucket_min[idx], num); bucket_max[idx] = max(bucket_max[idx], num); }for (int i = 1; i < cnt; ++i) {if (bucket_min[i] == INT_MAX || bucket_max[i] == INT_MIN) continue; res = max(res, bucket_min[i] - bucket_max[pre]); pre = i; }return res; }};
【C++实现LeetCode(164.求最大间距)】Github 同步地址:
https://github.com/grandyang/leetcode/issues/164
参考资料:
https://leetcode.com/problems/maximum-gap
http://blog.csdn.net/u011345136/article/details/41963051
https://leetcode.com/problems/maximum-gap/discuss/50642/radix-sort-solution-in-java-with-explanation
https://leetcode.com/problems/maximum-gap/discuss/50643/bucket-sort-java-solution-with-explanation-on-time-and-space
到此这篇关于C++实现LeetCode(164.求最大间距)的文章就介绍到这了,更多相关C++实现求最大间距内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Node.js中readline模块实现终端输入
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 人脸识别|【人脸识别系列】| 实现自动化妆