文章 224
评论 6
浏览 200768
Array - 164. Maximum Gap

Array - 164. Maximum Gap

164. Maximum Gap

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

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
  (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

  • You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
  • Try to solve it in linear time/space.

思路:

找出未排序数组排序后的最大间隔,一般如果是线性的时间复杂度,首先想到桶排序。

代码:

java:

class Solution {

    public int maximumGap(int[] nums) {

         int n = nums.length;
        if(n < 2) return 0;
        int min = nums[0];
        int max = nums[0];
        for(int i = 1;i < n;i++){
            if(min > nums[i]) min = nums[i];
            if(max < nums[i]) max = nums[i];
        }

        int gap = (max-min)/(n-1);
        if(gap == 0) gap++;
        int len = (max-min)/gap+1;
        int [] tmax = new int [len];
        int [] tmin = new int [len];

        for(int i = 0;i < n;i++){
            int index = (nums[i]-min)/gap;
            if(nums[i] > tmax[index]) tmax[index] = nums[i];
            if(tmin[index] == 0 || nums[i] < tmin[index]) tmin[index] = nums[i];
        }
        int myMax = 0;
        for(int i = 0;i < len;i++){
            if(myMax < tmin[i]-min) myMax = tmin[i]-min;
            if(tmax[i] != 0) min = tmax[i];
        }
        return myMax;
    }
}

标题:Array - 164. Maximum Gap
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/06/17/1560782771077.html

Nothing just happens, it's all part of a plan.

取消