Maximum Gap

描述

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

分析

这道题最直接的解法是,先排序,得到有序数组,然后相邻元素相减,找出差最大的,时间复杂度O(n log n)

然而本题要求O(n)时间,有没有O(n)的排序算法呢?桶排序、基数排序、计数排序。

解法1 桶排序

解法2 基数排序

解法3 计数排序

计数排序本质上是一种特殊的桶排序,当桶的个数最大的时候,就是计数排序。

本题用计数排序会MLE。

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/sorting/radix-sort/maximum-gap.html