LeetCode164. 最大间距-Java&Go-桶排序

• 算法
  • 1.桶排序思想，数组大小记为n
  • 2.首先遍历一遍数组找出max和min
  • 3.然后计算 minGap = ceil((max-min) / (n-1)) 得出可能的最小的“相邻元素之间最大的差值”
  • 4.然后第k个桶就存放范围在[min+(k-1)*minGap, min+k*minGap)的元素，共n-1个桶
  • 5.然后维护两个数组，一个存放每个桶中最小值，一个存放桶中的最大值
    • 因为我们只需要计算相邻元素之间最大的差值，这个差值肯定是大于每个桶的范围的，所以这个差值一定存在相邻的桶之间，是当前桶的最小值减去上一个桶的最大值；所以不用保存每个元素到桶中，只需要保留每个桶中的最大值最小值，用来计算相邻的桶的元素的差值
  • 6.最后根据两个数组计算相邻元素之间最大的差值

public int maximumGap(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }

    int n = nums.length;
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int x : nums) {
        min = Math.min(min, x);
        max = Math.max(max, x);
    }

    int minGap = (int) Math.ceil((double) (max - min) / (n - 1));
    int[] bucketMin = new int[n-1];
    int[] bucketMax = new int[n-1];
    Arrays.fill(bucketMin, Integer.MAX_VALUE);
    Arrays.fill(bucketMax, Integer.MIN_VALUE);
    for (int x : nums) {
        if (x == min || x == max) {
            continue;
        }
        int index = (x - min) / minGap;
        bucketMin[index] = Math.min(x, bucketMin[index]);
        bucketMax[index] = Math.max(x, bucketMax[index]);
    }

    int maxGap = Integer.MIN_VALUE;
    int prev = min;
    for (int i = 0; i < n - 1; i++) {
        if (bucketMin[i] == Integer.MAX_VALUE && bucketMax[i] == Integer.MIN_VALUE) {
            continue;
        }
        maxGap = Math.max(maxGap, bucketMin[i] - prev);
        prev = bucketMax[i];
    }
    maxGap = Math.max(maxGap, max - prev);
    return maxGap;
}

func maximumGap(nums []int) int {
    if nums == nil || len(nums) < 2 {
        return 0
    }

    n := len(nums)
    min := 1 << 31 - 1
    max := -1 << 31
    for _, x := range nums {
        if x < min {
            min = x
        }
        if x > max {
            max = x
        }
    }

    minGap := int (math.Ceil( float64 (max - min) / float64 (n - 1)))
    bucketMin := make([]int, n-1)
    bucketMax := make([]int, n-1)
    for i := range bucketMin {
        bucketMin[i] = 1 << 31 - 1
        bucketMax[i] = -1 << 31
    }
    for _, x := range nums {
        if x == min || x == max {
            continue
        }
        index := (x - min) / minGap
        if bucketMin[index] > x {
            bucketMin[index] = x
        }
        if bucketMax[index] < x {
            bucketMax[index] = x
        }
    }

    maxGap := -1 << 31
    prev := min
    for i := range bucketMin {
        if bucketMin[i] == 1 << 31 - 1 && bucketMax[i] == -1 << 31 {
            continue
        }
        if maxGap < bucketMin[i] - prev {
            maxGap = bucketMin[i] - prev
        }
        prev = bucketMax[i]
    }
    if maxGap < max - prev {
        maxGap = max - prev
    }
    return maxGap
}

• 算法
  • 1.直观解法
  • 2.首先排序
  • 3.然后寻找相邻元素之间最大差值

public int maximumGap(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }

    Arrays.sort(nums);
    int result = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i+1] - nums[i] > result) {
            result = nums[i+1] - nums[i];
        }
    }
    return result;
}

func maximumGap(nums []int) int {
    if nums == nil || len(nums) < 2 {
        return 0
    }

    sort.Ints(nums)
    result := 0
    for i := 0; i < len(nums) - 1; i++ {
        if nums[i+1] - nums[i] > result {
            result = nums[i+1] - nums[i]
        }
    }
    return result
}