LeetCode 164. Maximum Gap (排序)
LeetCode 164. Maximum Gap (排序)
ShenduCC
发布于 2020-02-14 15:04:31
发布于 2020-02-14 15:04:31
题意：就是给你一个数组，让你输出排好序后，相邻元素差值最大的那个差值。
题解：首先，当然我们可以用快排，排完序之后，遍历一遍数组，就能得到答案了。但是快速排序的效率是O(n* logn)，不是题目要求的线性效率，也就是O(n)的效率。
那么诸多排序算法中，也是由线性效率的排序算法，当然这些算法的目标是线性效率，而在实际情况中的效率也并不是最快的。首先就是基数排序，基数排序的效率是O(n*k)，
k 是由元素的位数决定的。
线性时间的排序还有一个桶排序，桶排序，一开始选择一些桶，每个桶代表一个范围区间，把数字按部就班放到桶里，然后在桶里再继续排序，（可以继续递归用桶排序，也可以用别的排序）。
在这道题目中，桶排序是最好的选择，因为如果使用桶排序，则无需将整个数组都排序，题目要求的是排好序之后的相邻元素的最大差值。
假设最小值是min，最大值是max，数组的个数是n。那么假设这n个数字在min和max之间平均分布， k = (min-max)/(n-1) 代表相邻元素之间的差值。现在假设n个数字不是平均分布的，就是任意哪种情况，那么相邻元素之间的差值永远都是大于K的，这是可以证明的。所以确定了min,max,n,那么相邻元素的最大差值都是必定大于等于k的。
所以我们的每个桶的大小（区间范围）设为k，这样答案就在桶和桶之间，而不存在桶里，所以我们在第一次按部就班的放到桶里之后，直接比较桶之间差值，就能得出答案了。
效率是O(n+t), t就是桶的数量，(max-min)/k+1
基数排序
class Solution {
public:
vector<int> a[10];
vector<int> b[10];
int maximumGap(vector<int>& nums) {
int n = nums.size();
if(n<2)
return 0;
int m=0;
for(int i=0;i<n;i++)
{
m=max(m,MaxBit(nums[i]));
}
for(int i=0;i<m;i++)
{
if(i==0)
{
for(int j=0;j<n;j++)
{
int x=Bit(nums[j],i);
a[x].push_back(nums[j]);
}
}
else
{
for(int j=0;j<10;j++)
{
for(int k=0;k<b[j].size();k++)
{
int x=Bit(b[j][k],i);
a[x].push_back(b[j][k]);
}
}
}
for(int j=0;j<10;j++)
{
b[j].clear();
for(int k=0;k<a[j].size();k++)
{
b[j].push_back(a[j][k]);
}
a[j].clear();
}
}
int ans=0;
int l=-1;
for(int i=0;i<10;i++)
{
for(int j=0;j<b[i].size();j++)
{
if(l==-1)
{
l=b[i][j];
continue;
}
ans=max(ans,b[i][j]-l);
l=b[i][j];
}
}
return ans;
}
int Bit(int x,int pos)
{
while(pos)
{
x/=10;
pos--;
}
return x%=10;
}
int MaxBit(int x)
{
int ax=0;
while(x)
{
ax++;
x/=10;
}
return ax;
}
};桶排序
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.size()<2)
return 0;
int m = nums[0];
int n = nums[0];
int len = nums.size();
for(int i=1;i<nums.size();i++)
{
m = max(m,nums[i]);
n = min(n,nums[i]);
}
int t = max(1,(m-n)/(len-1));
int num = (m-n) / t + 1;
int a[num];
int b[num];
memset(a,-1,sizeof(a));
memset(b,-1,sizeof(b));
for(int i=0;i<nums.size();i++)
{
int index = (nums[i]-n)/t;
if(a[index]==-1)
a[index]=nums[i];
else
a[index]=min(a[index],nums[i]);
if(b[index]==-1)
b[index]=nums[i];
else
b[index]=max(b[index],nums[i]);
}
int ans=0;
int l=-1,r=-1;
for(int i=0;i<num;i++)
{
if(a[i]!=-1)
{
r=a[i];
if(l!=-1)
ans=max(ans,r-l);
l=b[i];
}
}
return ans;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读