漫画算法:无序数组排序后的最大相邻差值

小灰一边回忆一边讲述起当时面试的情景……

题目:有一个无序整型数组,如何求出这个数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。(例如:无序数组 2,3,1,4,6,排序后是1,2,3,4,6,最大差值是6-4=2)

解法一:

用一种较快的稳定排序算法(比如归并算法,时间复杂度N*logN)给原数组排序,然后遍历排好序的数组,每两个相邻元素求差,最终得到最大差值。

该解法的时间复杂度是O(N*logN),在不改变原数组的情况下,空间复杂度是O(N)。

解法二:

1.利用计数排序的思想,先求出原数组的最大值Max与最小值Min的区间长度k(k=Max-Min+1)。

2.创建一个长度为k的新数组Array。

3.遍历原数组,把原数组每一个元素插入到新数组Array对应的位置,比如元素的值为n,则插入到Array[n-min]当中。此时Array的部分位置为空,部分位置填充了数值。

4.遍历新数组Array,统计出Array中最大连续出现空值的次数+1,即为相邻元素最大差值。

例如给定无序数组 { 2, 6, 3, 4, 5, 10, 9 },处理过程如下图:

该解法的时间复杂度为O(n+k),空间复杂度同样是O(n+k)。

解法三:

1.利用桶排序的思想,先求出原数组从最小值Min到最大值Max的单位区间长度d,d=(Max-Min)/n。算出d的作用是为了后续确定各个桶的区间范围划分。

2.创建一个长度是N+1的数组Array,数组的每一个元素都是一个List,代表一个桶。

3.遍历原数组,把原数组每一个元素插入到新数组Array对应的桶当中,进入各个桶的条件是根据不同的数值区间(数值区间如何划分,看后面的图就明白了)。由于桶的总数量是N+1,所以至少有一个桶是空的。

4.遍历新数组Array,计算每一个空桶右端非空桶中的最小值,与空桶左端非空桶的最大值的差,数值最大的差即为原数组排序后的相邻最大差值。

例如给定无序数组 { 0, 6, 3, 16, 7, 10, 9, 11, 20, 18 },处理过程如下图:

该解法的时间复杂度为O(n),空间复杂度同样是O(n)。

十分钟后……

以上就是小灰面试的情况……

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

1 7 收藏 3 评论

关于作者:玻璃猫

互联网公司的码农一枚,喜欢算法和面向对象设计。个人微信号:13522239721 个人订阅号:dreamsee321欢迎一起交流讨论! 个人主页 · 我的文章 · 96 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部