相邻两数最大差值

太过爱你忘了你带给我的痛 2022-06-09 02:07 160阅读 0赞

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。

给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。

# 测试样例：
    [1,2,5,4,6],5
    返回：2

**我的提交**

# -*- coding:utf-8 -*-
    
    class Gap:
        def maxGap(self, A, n):
            # write code here
            minValue = min(A)
            maxValue = max(A)
            bucketNum = (maxValue - minValue ) // 2 + 1
            buckets = [[] for _ in range(bucketNum)]
    
            for num in A:
                buckets[(num - minValue) // 2].append(num)
    
            maxdiff = 0
            lastMax = max(buckets[0])
            nowMin = 0
            for i in range(1, bucketNum):
                if buckets[i] == []:
                    continue
                nowMin = min(buckets[i])
                maxdiff = max(maxdiff, nowMin - lastMax)
                lastMax = max(buckets[i])
            return maxdiff
    
    if __name__ == '__main__':
        g = Gap()
        print(g.maxGap([1,2,5,4,6],5))

**参考答案**

python

# -*- coding:utf-8 -*-
    
    class Gap:
        def maxGap(self, A, n):
            # write code here
            maxVal,minVal = max(A),min(A)
            hashTable = [[maxVal,minVal,0] for i in xrange(0,n + 1)]
            for x in A:
                ind = (x - minVal) * n // (maxVal - minVal)
                hashTable[ind][2] += 1
                hashTable[ind][0] = min(hashTable[ind][0],x)
                hashTable[ind][1] = max(hashTable[ind][1],x)
            diffMax = 0
            preMax = maxVal
            for x in hashTable:
                if x[2] == 0:
                    continue
                diffMax = max(x[0] - preMax,diffMax)
                preMax = x[1]
            return diffMax

java

import java.util.*;
    
    public class Gap { 
        public int maxGap(int[] nums,int N) {
            if (nums == null || nums.length < 2) {
                return 0;
            }
            int len = nums.length;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
            if (min == max) {
                return 0;
            }
            boolean[] hasNum = new boolean[len + 1];
            int[] maxs = new int[len + 1];
            int[] mins = new int[len + 1];
            int bid = 0;
            for (int i = 0; i < len; i++) {
                bid = bucket(nums[i], len, min, max); // 算出桶号
                mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
                maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
                hasNum[bid] = true;
            }
            int res = 0;
            int lastMax = 0;
            int i = 0;
            while (i <= len) {
                if (hasNum[i++]) { // 找到第一个不空的桶
                    lastMax = maxs[i - 1];
                    break;
                }
            }
            for (; i <= len; i++) {
                if (hasNum[i]) {
                    res = Math.max(res, mins[i] - lastMax);
                    lastMax = maxs[i];
                }
            }
            return res;
        }
    
        // 使用long类型是为了防止相乘时溢出
        public int bucket(long num, long len, long min, long max) {
            return (int) ((num - min) * len / (max - min));
        }
    }