算法：无序实数列V[N]中大小相邻实数的最大差（线性空间和线性时间）
题： 有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间
题目来自CSDN论坛里的讨论，很多网友给出了他们的意见。
其实这个问题要求线性时间条件下，通常会让我们想到桶排序；接着关键是考虑怎么减少桶排序中对桶中各数的排序即可想到解决方法。我的算法如下：
- 主要是先找出最大的数与最小的数，然后构造一个n个桶，桶的下标与数的关系为： index = (v[i]-min)/(max-min/n).
- 遍历数列，将数值插入到对应的桶中。每个桶最多保留最小和最大的两个元素，不需要多余的数。
- 遍历所有的桶，记录每个桶之间有多少个空桶到数据flags中，并求出最大连续空桶数 maxGap。
- 最后遍历flags数组，对于空桶数 >= maxGap -1 的元素，计算从前面的最近的不为空的桶中的大元素与当前桶中的最小元素的差，最终找出最大差。
主算法：
max,min ← GetMaxAndMin (v) bucks[n]; for i = 0 to n-1 buckNo ← get buck no: (v[i]-min) / (max-min/n) //计算桶下标（如果不为整数，取较小的数的绝对值） if buck[ buckNo ] is empty: insert v[i] if buck[buckNo].length == 1 : //insert v[i] 与原来的数构成正序关系 if buck[buckNo].length == 2 : //与原来的2元素按正序关系排列，去掉中间的数，仍然是2个元素 // 标记每个不为空的桶元素之前有多少个空桶 flags[n]; //记录每个桶之前的空桶数目 maxgaps = 0; tempgaps = 0; for i ← FindFirstNotEmptyBuck (bucks) to n-1 if buck[i] is empty then tempgaps ++ else flags[i] ← tempgaps; maxgaps ← GetMax (tempgaps, maxgaps) tempgaps = 0; // 计算最大的相邻的最大值 maxNeighbor == null; for i ← 0 to n-1 if maxgaps - flag[i] < 2 then maxNeighbor ← GetMax(COMPUTE_MAX(bucks,i,flag[i]), maxNeighbor) return maxNeighbor
COMPUTE_MAX(bucks,i,gap) : //常数级别，取头或取尾 return GetMinEle(bucks, i) - getMaxEle(bucks, i - gap -1) <pre lang="c">GetMaxAndMin (v): max, min, i n ← v.length if n%2 == 0 then if V[1] > V[0] then max ← V[1]; min ← V[0]; else max ← V[0]; min ← V[1]; i = 2; else max = min = V[0]; i = 1; for i to n-2 if v[i+1] > v[i] then min ←GetMin(min, v[i]); max ← GetMax(max, v[i+1]) else min ←GetMin(min, v[i+1]); max ← GetMax(max, v[i]) i++; //每次取两个数 return (max,min)
FindFirstNotEmptyBuck (bucks) for i ← 0 to n-1 if tempgapstart == -1 then if buck[i] is empty then break else continue; return i;
Related posts:
Recent Comments