算法-leecode164-最大间距

2022-4-13 diaba 算法 

package com.jiucaiyuan.net.question;

import java.util.Arrays;

/**
 * 给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
 * <p>
 * 您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。
 * <p>
 * 示例1:
 * <p>
 * 输入: nums = [3,6,9,1]
 * 输出: 3
 * 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
 * 示例2:
 * <p>
 * 输入: nums = [10]
 * 输出: 0
 * 解释: 数组元素个数小于 2，因此返回 0。
 *
 * @Author jiucaiyuan  2022/4/13 23:41
 * @mail services@jiucaiyuan.net
 */
class MaximumGapInOrderedArray {
    public static int maximumGap(int[] nums) {
        //特殊情况判断
        if (nums.length < 2) {
            return 0;
        }
        if (nums.length == 2) {
            return Math.abs(nums[0] - nums[1]);
        }
        //找到最大值 获取最多的位数
        int max = Arrays.stream(nums).max().getAsInt();
        int length = String.valueOf(max).length();
        nums = radixSort(nums, length);
        int gap = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            int tmp = nums[i] - nums[i - 1];
            if (tmp > gap) {
                gap = tmp;
            }
        }
        return gap;
    }

    private static int[] radixSort(int[] nums, int length) {
        //在每一位上进行排序 
        for (int i = 1; i <= length; i++) {
            nums = countingSort(nums, i);
        }
        return nums;
    }

    //计数排序
    private static int[] countingSort(int[] nums, int b) {
        int[] countArray = new int[10];
        for (int i = 0; i < nums.length; i++) {
            countArray[getValue(nums[i], b)] += 1;
        }
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        int[] res = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int val = getValue(nums[i], b);
            res[countArray[val] - 1] = nums[i];
            countArray[val] -= 1;
        }
        return res;
    }

    //获取整形num的第b个数字 从右往左数
    private static int getValue(int num, int b) {
        return num / (int) (Math.pow(10, b - 1)) % 10;
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 2, 7, 4, 9, 2, 14};
        System.out.println(maximumGap(nums));
    }
}

« 算法-leecode46-全排列 | JVM垃圾回收»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022