LeetCode -- Maximum Gap

LeetCode -- 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.


本題直接使用.net內置（或其他編程語言）的排序算法就可以，然後計算間隔找出最大的就行了。






以下是一種最簡單的實現方式，調用 LINQ的sort（內部實現為stable的快排）然後計算間隔。

public class Solution {
    public int MaximumGap(int[] nums) 
    {
        if(nums == null || nums.Length < 2){
    		return 0;
    	}
    	
    	var lst = nums.OrderBy(n=>n).ToList();
    	var max = 0;
    	for(var i = 0;i < lst.Count - 1; i++){
    		max = Math.Max(max, lst[i+1] - lst[i]);
    	}
    	
    	return max;
    }




}

官方的答案是使用桶排：
1. 求出最大最小值，一共需要nums.Length / (max - min)個桶
2. 遍歷nums的過程中判斷nums[i]屬於哪個桶，然後將元素放入指定的桶中
3. 維護每個桶的最大最小值
4. 遍歷桶的最值，它們之間的間隔(bucket[i-1]的最小值與bucket[i]的最大值)



 

public class Solution {
    public int MaximumGap(int[] nums) 
    {
        if(nums == null || nums.Length < 2){
    		return 0;
    	}
    	
    	// find the max and min
    	int max = nums[0];
        int min = nums[0];
        for(int i = 1; i < nums.Length; i++){
            max = Math.Max(max, nums[i]);
            min = Math.Min(min, nums[i]);
        }
     
        // init bucket
        var buckets = new Bucket[nums.Length + 1];
        for(int i=0; i < buckets.Length; i++){
            buckets[i] = new Bucket();
        }
     
        double height = (double) nums.Length / (max - min);// bucket height
        
        // loop each element in nums, find the bucket for it.
        for(int i=0; i