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

   <p style="text-align: center;"><img src="https://simg.open-open.com/show/3ebe8f0ea823cd25cfda31285fad5526.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/ee01434a4935eadd9dd95e1244383a49.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/fe7305d0d96a72b2180734e0d10d794d.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/fb9a69a2baa54b9ae98e1821cf602f69.jpg"></p>    <p>小灰一边回忆一边讲述起当时面试的情景……</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/60d56e906d41cbe52267cc7ff70eb25c.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/741e67d6b7247e80f42f14fc9bf17fc8.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/ff42df12e4ffc5c530832ccd873126da.jpg"></p>    <p>题目：有一个无序整型数组，如何求出这个数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。（例如：无序数组 2,3,1,4,6，排序后是1,2,3,4,6，最大差值是6-4=2）</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/bea30911026e7552acd177d0886fa574.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/eb371633d00c281faa93367ce2cdec1c.jpg"></p>    <h3>解法一：</h3>    <p>用一种较快的稳定排序算法（比如归并算法，时间复杂度N*logN）给原数组排序，然后遍历排好序的数组，每两个相邻元素求差，最终得到最大差值。</p>    <p>该解法的时间复杂度是O（N*logN），在不改变原数组的情况下，空间复杂度是O（N）。</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/1ed8c7050cbe804b2cdb3a51dcfb9446.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/bea30911026e7552acd177d0886fa574.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/f31de7c34367112351f7be19e923bc2c.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/007055e2d39b01ae14494b52832eac58.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/09b1054e1611c58fac9454e1fcf1d503.jpg"></p>    <h3>解法二：</h3>    <p>1.利用计数排序的思想，先求出原数组的最大值Max与最小值Min的区间长度k（k=Max-Min+1）。</p>    <p>2.创建一个长度为k的新数组Array。</p>    <p>3.遍历原数组，把原数组每一个元素插入到新数组Array对应的位置，比如元素的值为n，则插入到Array[n-min]当中。此时Array的部分位置为空，部分位置填充了数值。</p>    <p>4.遍历新数组Array，统计出Array中最大连续出现空值的次数+1，即为相邻元素最大差值。</p>    <p>例如给定无序数组 { 2, 6, 3, 4, 5, 10, 9 }，处理过程如下图：</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/658906dc1f591717d6b55a8e33e09bc8.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/2a448b74f7d6dd346df6b14ce8a33da5.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/d3f217add2eda543adbd7369c5bd1a46.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/137bf045f4dbea4c6f297614a7c8a962.jpg"></p>    <p>该解法的时间复杂度为O（n+k），空间复杂度同样是O（n+k）。</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/089a31f73d8dcc2dee05f9b02f89d6e0.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/db52e2445cf96bdf61e8c0e9c808e598.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/bea30911026e7552acd177d0886fa574.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/e6fb825c94bc7731ece56f358431466a.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/7228634527aaefd20f3518ffe8dde6c3.jpg"></p>    <h3>解法三：</h3>    <p>1.利用桶排序的思想，先求出原数组从最小值Min到最大值Max的单位区间长度d，d=(Max-Min)/n。算出d的作用是为了后续确定各个桶的区间范围划分。</p>    <p>2.创建一个长度是N+1的数组Array，数组的每一个元素都是一个List，代表一个桶。</p>    <p>3.遍历原数组，把原数组每一个元素插入到新数组Array对应的桶当中，进入各个桶的条件是根据不同的数值区间（数值区间如何划分，看后面的图就明白了）。由于桶的总数量是N+1，所以至少有一个桶是空的。</p>    <p>4.遍历新数组Array，计算每一个空桶 <strong>右端非空桶中的最小值</strong> ，与空桶 <strong>左端非空桶的最大值</strong> 的差，数值最大的差即为原数组排序后的相邻最大差值。</p>    <p>例如给定无序数组 { 0, 6, 3, 16, 7, 10, 9, 11, 20, 18 }，处理过程如下图：</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/38d215caa93c4d68af491b0fa29b4228.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/775f9ad6e3e3fcb0c4f86f082c3ea939.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/d887d70e6679e7874a8a9ba0f9c43238.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/6429e46cfea35732f885fc9cf20b169d.jpg"></p>    <p>该解法的时间复杂度为O（n），空间复杂度同样是O（n）。</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/a499b9a3791869ace6175e1cd886155d.jpg"></p>    <p>十分钟后……</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/ea4fa46048288ceda7c078d38afa35fd.jpg"></p>    <p>以上就是小灰面试的情况……</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/dcb3a2c161c632254335f1015e08eae2.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/0bfb17e1e739debb8901ac17c0a83fc1.jpg"></p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/96e2227dedf30212b02b0fda97fc1fda.jpg"></p>    <p> </p>    <p> </p>    <p>来自：http://blog.jobbole.com/108594/</p>    <p> </p>