164. Maximum Gap

难度: Medium

题目描述

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

 

Example 1:

Input: nums = [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: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

解题思路

代码实现

解决方案

java

class Solution {
    public int maximumGap(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);

        }
        int[] tempArray = new int[set.size()];
        int i = 0;
        for (Integer e : set) {
            tempArray[i++] = e;
        }
        sort(tempArray);
        return findMaxGap(tempArray);

    }

    private int findMaxGap(int[] arr) {
        if (arr == null || arr.length == 1) {
            return 0;
        }
        if (arr.length == 2) {
            return Math.max(arr[0] - arr[1], arr[1] - arr[0]);
        }
        int maxGap = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - arr[i-1] > maxGap) {
                maxGap = arr[i] - arr[i-1];
            }
        }
        return maxGap;
    }

    private void sort(int[] arr) {
        if (arr == null || arr.length == 1) {
            return;
        }
        int exp = 1;
        
        int maxValue = Arrays.stream(arr).max().getAsInt();
        // 临时数组，用于存放排序过程中的结果
        int[] buf = new int[arr.length];
        while (maxValue >= exp) {
            int[] count = new int[10];
            for (int i = 0; i < arr.length; i++) {
                count[(arr[i] / exp) % 10]++;
            }

            for (int i = 1; i < count.length; i++) {
                count[i] += count[i - 1];
            }
            for (int i = arr.length-1; i >-1; i--) {
                int digit = (arr[i] / (int) exp) % 10;
                buf[count[digit] - 1] = arr[i];
                count[digit]--;
            }
            // 将排序结果复制回原数组
            System.arraycopy(buf, 0, arr, 0, arr.length);
            // 增加基数，准备下一轮排序
            exp *= 10;
        }
    }

}