✡ leetcode 164. Maximum Gap 寻找最大相邻数字差 --------- java

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.

给定一个未排序的数组，然后找出排序之后的数组中，相邻数字的最大差。

1、桶排序

public class Solution {

    public int maximumGap(int[] nums) {

        int len = nums.length;

        if (len < 2){

            return 0;

        }

        int max = nums[0];

        int min = nums[0];

        for (int num : nums){

            if (max < num){

                max = num;

            } else if ( min > num){

                min = num;

            }

        }

        int gap = (max-min)/(len-1);

        if( gap == 0){

            gap = 1;

        }

        int size = (max - min) / gap + 1;

        int[] gapMax = new int[size];

        int[] gapMin = new int[size];

        for (int num : nums){

            int pos = (num - min)/gap;

            if (gapMax[pos] < num){

                gapMax[pos] = num;

            }

            if (gapMin[pos] == 0 || gapMin[pos] > num){

                gapMin[pos] = num;

            }

        }

        int start = min;

        int end = gapMax[0];

        int result = end - start;

        for (int i = 0; i < size - 1; i++){

            start = gapMax[i] == 0 ? start : gapMax[i];

            end = gapMin[i+1];

            if (result < (end - start)){

                result = end - start;

            }

        }

        if (gapMax[size - 1] == 0 && end - start > result){

            result = end - start;

        } else if (gapMax[size - 1] != 0 && end - gapMax[size - 1] > result){

            result = end - gapMax[size - 1];

        }

        return result;

    }

}

巴特西

✡ leetcode 164. Maximum Gap 寻找最大相邻数字差 --------- java

最新文章

热门文章