无序数组 排序后 最大间隔
本文现转载他人文章,后续会进行详细讲解。
1 无序数组 排序后 最大间隔
原题:给你n个任意整数,求排序后相邻两个数之间的最大差值,这里n可能有10^5,整数为任意32位整型。要求求解算法的时间复杂度为O(n)。
1.1 思路:不排序的桶排序
原文链接:https://blog.csdn.net/xindoo/article/details/52821167
回到题目, 首先说明一点,这题的大体思路就是桶排序,但是,不需要全部排序,只需要大体有序,其实就是每个桶内的数不需要有序,接下来我将解释为什么桶内的数不需要排序。
n个任意的数,划分到n个桶里。首先第一种情况,如果恰好每个桶都只有一个数,划分后不就恰好有序了吗,有序这道题不就好解决了吗! 另一种情况,在每个数数值范围非常大的时候也是很常见的,就是数不会均匀的落到每个桶中,这题的主要难点也在这。
如何解决? 想想看,在任意一个桶内任何情况下任意俩数的最大差值是多少,最大不就是桶的大小减一吗? 但是,在全局中肯定存在两个桶,后面一个桶的最小值和前一个桶的最大值差值大于桶大小,且这两个桶之间不存在其他有数存在的桶,即都是空桶。 换种牵线的说法,绝对存在bucket[j].min - bucket[i].max > bucket[i].size-1(j > i且 i和j之间无其他非空桶)。理解了这点,此题得解。
其实我们只需要遍历次数组,找出最大最小值,然后安装最大最小值,将其他数划分到n个桶里。然后求连续两个非空桶i j的bucket[j].min - bucket[i].max的最大值即可。
想想看,因为我们只需要用到每个桶的最大最小值,所以不需要在每个桶中保存所有的值,只需要最大最小值而已。
1.2 程序实现
原文链接:https://blog.csdn.net/u010601662/article/details/79271370
int maxGap(std::vector<int> &vecNum)
{
// 获取最大值与最小值
int nMax = vecNum[0], nMin = vecNum[0];
for (int nIndex = 1; nIndex < vecNum.size(); nIndex++)
{
if (nMax < vecNum[nIndex])
{
nMax = vecNum[nIndex];
}
else if (nMin > vecNum[nIndex])
{
nMin = vecNum[nIndex];
}
}
// 桶的个数
int nBucketNum = vecNum.size() + 1;
// 每个桶的区间长度
int nBucketLength = (nMax - nMin) / vecNum.size();
// 记录桶的最小值
std::vector<int> vecBucketMin(nBucketNum, INT_MAX);
// 记录桶的最大值
std::vector<int> vecBucketMax(nBucketNum, INT_MIN);
// 获取每个桶内的最小和最大值
for (int nIndex = 0; nIndex < vecNum.size(); nIndex++)
{
// 映射到某一个桶
int nBucketIndex = (vecNum[nIndex] - nMin) / nBucketLength;
// 记录桶的最大和最小值
if (vecBucketMax[nBucketIndex] < vecNum[nIndex])
{
vecBucketMax[nBucketIndex] = vecNum[nIndex];
}
if (vecBucketMin[nBucketIndex] > vecNum[nIndex])
{
vecBucketMin[nBucketIndex] = vecNum[nIndex];
}
}
// 计算每一个空桶右端非空桶中的最小值,与空桶左端非空桶的最大值的差
int nMaxGap = 0;
int nPreMax = vecBucketMax[0];
bool nEmptyBucket = false;
for (int nBucketIndex = 1; nBucketIndex < nBucketNum; nBucketIndex++)
{
if (vecBucketMin[nBucketIndex] != INT_MAX)
{
// 非空桶
if (nEmptyBucket)
{
// 前一个是空桶
nMaxGap = vecBucketMin[nBucketIndex] - nPreMax;
}
nPreMax = vecBucketMax[nBucketIndex];
nEmptyBucket = false;
}
else
{
// 空桶
nEmptyBucket = true;
}
}
return nMaxGap;
}
下一篇: php5.3 注意事项说明_php技巧