首页 > 代码库 > Maximum Gap
Maximum Gap
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.
class Solution{public: int maximumGap(vector<int>& nums){ int n = nums.size(); if( n < 2) return 0; int maxVal = *max_element(nums.begin(),nums.end()); int minVal = *min_element(nums.begin(),nums.end()); if( maxVal == minVal) return 0; int gap = int((maxVal-minVal)/n+1); vector<int> maxofBucket(n,INT_MIN); vector<int> minofBucket(n,INT_MAX); for(int i=0;i<n;i++){ int bucketId = int((nums[i]-minVal)/gap); maxofBucket[bucketId] = max(nums[i],maxofBucket[bucketId]); minofBucket[bucketId] = min(nums[i],minofBucket[bucketId]); } int preMax = maxofBucket[0]; int res = INT_MIN; for(int i=1;i<n;i++){ if(minofBucket[i] != INT_MAX){ res = max(res,minofBucket[i]-preMax); preMax = maxofBucket[i]; } } return res; }};
Maximum Gap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。