注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex164 Maximum Gap  

2015-05-31 16:25:37|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


找到一堆数组里面的排序后最大的gap。其实这题并不难,难就难在题目要求o(n)的复杂度,普通的排序都是nlogn的复杂度,所以这里不能用常规的排序,只能用线性排序的方法,比如计数、桶排序等等。
先上普通排序的方法

int common(vector<int> nums)
{
sort(nums.begin(),nums.end()); //nlogn的复杂度 很明显是不行的
int len = nums.size();
int maxGap = INT_MIN;
for (int i = 1; i < len; i++)
{
maxGap = myMax(maxGap, nums[i] - nums[i - 1]);
}
return maxGap;
}
int myMax(int a,int b)
{
return a > b ? a : b;
}
int myMin(int a, int b)
{
return a > b ? b : a;
}

后来参考别人的桶排序的方法,我们假设数据是平均分布的,那么数组的大小是n,所以分配n个桶。如果每个桶里面都放一个,那么最大距离就是桶之间的最大距离;如果有的桶是空桶,因为桶的距离是平均的,桶内得距离不会超过桶间的距离(我是这么理解的),所以还是求桶之间的最大距离。所以两个数组维护每个桶的最大值最小值就可以,桶内不必排序,这样就能做到线性的了。我照着这个思路写代码,可是oj上不通过,貌似有错误

/*
* 我表示开始的时候没有理解题意
* 题目的意思是返回其排序后最大的max gap
* 要求线性时间空间
* 这样就不能用一般的比较排序了 因为普通的比较排序有一个下界线 nlogn
* 所以只能用其他的排序方法
*/
class Solution {
public:
int maximumGap(vector<int>& nums) {
int len = nums.size();
if (len < 2) return 0;
return buckerOrder(nums);

}
int buckerOrder(vector<int> nums)
{
//使用桶排序,有多少个元素就有多少个桶, 擦 这都行(前提是他均匀分布的)
//自然其空间时间复杂度就是线性的了
// 第一步就算每个桶里面的最大元素和最小元素
//算出来之后求前一个桶和后一个桶里面的大gap,取最大值

//这个提交了貌似有问题
int maxVal = *max_element(nums.begin(),nums.end());
int minVal = *min_element(nums.begin(), nums.end());

int avergeGap = ceil((double)(maxVal - minVal) / (nums.size() - 1)); //安排桶的数量
int bucketNum = ceil((double)(maxVal - minVal) / avergeGap);
vector<int> bucketMin(bucketNum, INT_MAX);
vector<int> bucketMax(bucketNum, INT_MIN);
int i;
int bucketId;
for (i = 0; i < bucketNum; i++)
{
if (nums[i] != maxVal&&nums[i] != minVal)
{
bucketId = (nums[i] - minVal) / avergeGap;
bucketMin[bucketId] = myMin(bucketMin[bucketId],nums[i]);
bucketMax[bucketId] = myMax(bucketMax[bucketId], nums[i]);
}
}
int maxGap = INT_MIN;
int previous = minVal;
for (i = 0; i < bucketNum; i++)
{
//考虑一下桶是空的情况
if (bucketMin[i] == INT_MAX || bucketMax[i] == INT_MIN)
continue;
maxGap = myMax(maxGap,bucketMin[i]-previous);
previous = bucketMax[i];
}
maxGap = myMax(maxGap,maxVal-previous);
return maxGap;
}
int common(vector<int> nums)
{
sort(nums.begin(),nums.end()); //nlogn的复杂度 很明显是不行的
int len = nums.size();
int maxGap = INT_MIN;
for (int i = 1; i < len; i++)
{
maxGap = myMax(maxGap, nums[i] - nums[i - 1]);
}
return maxGap;
}
int myMax(int a,int b)
{
return a > b ? a : b;
}
int myMin(int a, int b)
{
return a > b ? b : a;
}
};

可是几乎的同样的代码,别人的就可以通过,我目前还不知道问题在什么地方

/*
* 我表示开始的时候没有理解题意
* 题目的意思是返回其排序后最大的max gap
* 要求线性时间空间
* 这样就不能用一般的比较排序了 因为普通的比较排序有一个下界线 nlogn
* 所以只能用其他的排序方法
*/
class Solution {
public:
int maximumGap1(vector<int> &num) {
//这个是好的
if (num.size() < 2) return 0;
// 1. 算出用的桶数:取平均间隔,再用最大值和最小值之差除以间隔,得到桶数
// 因为假设所有值都是平均分布的时候,如此取桶数可得时间复杂度是0(n)
auto maxVal = *max_element(num.begin(), num.end());
auto minVal = *min_element(num.begin(), num.end());
int agGap = ceil((double)(maxVal - minVal) / (num.size() - 1)); // 平均间隔
int bucketCount = ceil((double)(maxVal - minVal) / agGap);
// 2. 记录每个桶的最大值和最小值
vector<pair<int, int> > buckets(bucketCount, make_pair(INT_MIN, INT_MAX)); // 初始化桶
for (auto val : num){
if (val == maxVal || val == minVal) continue;
int bucketNum = (val - minVal) / agGap;
if (val > buckets[bucketNum].first)
buckets[bucketNum].first = val; // 存储最大值
if (val < buckets[bucketNum].second) buckets[bucketNum].second = val; // 存储最小值
}
// 3. 算出最大间隔
int maxGap(0), lastMax(minVal);
for (auto bucket : buckets){
if (bucket.first == INT_MIN) continue; // 空桶
int curMax(bucket.first), curMin(bucket.second);
maxGap = max(maxGap, curMin - lastMax);
lastMax = curMax;
}
maxGap = max(maxGap, maxVal - lastMax);
return maxGap;
}
};



参考
http://www.cnblogs.com/skysand/p/4179099.html
http://www.cnblogs.com/ganganloveu/p/4162290.html
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017