桶排序思想运用

发布时间:2024年01月21日

/**

  • @author Lei
  • @date 2024/1/17
  • 给定一个数组,求如果排序之后,相邻两数的最大差值,要求时
  • 间复杂度O(N),且要求不能用非基于比较的排序。
  • n个数用n+1个桶装,一定会有一个空桶,每个桶间隔相等,那么最大差值一定不会是一个桶内的元素的差。通过每个桶的最大值和后一个桶的最小值计算差值。
    */
public class MaxGap {

    public static int maxGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int len = arr.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i : arr) {
            max = Math.max(i, max);
            min = Math.min(i, min);
        }
        if (max == min) {
            return 0;
        }
        int[] maxArray = new int[len + 1];
        int[] minArray = new int[len + 1];
        boolean[] hasNum = new boolean[len + 1];
        int t = 0;
        for (int j : arr) {
            t = bucket(j, len, min, max);
            maxArray[t] = hasNum[t] ? Math.max(maxArray[t], j) : j;
            minArray[t] = hasNum[t] ? Math.min(minArray[t], j) : j;
            hasNum[t] = true;
        }
        int res = 0;
        int lastMax = maxArray[0];
        for (int i = 1; i <= len; i++) {
            if (hasNum[i]) {
                res = Math.max(res, minArray[i] - lastMax);
                lastMax = maxArray[i];
            }
        }
        return res;
    }

    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }


    // for test

    public static int comparator(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int gap = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            gap = Math.max(nums[i] - nums[i - 1], gap);
        }
        return gap;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (maxGap(arr1) != comparator(arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}
文章来源:https://blog.csdn.net/Casual_Lei/article/details/135713819
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。