【趣谈算法系列】：无序数组排序后的最大相邻差值

正文

请到「今天看啥」查看全文

解法一：

用一种较快的稳定排序算法（比如归并算法，时间复杂度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，即为相邻元素最大差值。

请到「今天看啥」查看全文