力扣164最大间距-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣164最大间距。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.前言

因为昨天写了一个基数排序，今天我来写一道用基数排序实现的题解，希望可以帮助你理解基数排序。

这个题本身不难，就是线性时间和线性额外空间(O(n))的算法，有点难实现

基数排序的时间复杂度是O(d*(n+radix))，其中d是最大值的位数，n是数组长度，radix是基数（10）然后化简就是 O(n)

力扣164最大间距,leetcode,算法,排序算法

2.思路分析

首先，找到待排序数组中的最大值，确定最大值的位数。假设最大值是max，位数是d。
创建10个桶（0-9），每个桶用来存放对应位数上的数字。
从低位（个位）开始，根据当前位数的值将待排序数组中的数字放入对应的桶中。
将桶中的数字按照顺序取出，覆盖原数组，然后进入下一位数的排序。
重复步骤3和步骤4，直到排完最高位（即 d 位）。
最后，遍历排序后的数组，计算相邻数字之间的差值，找到最大的差值，即为最大间距。

3.代码实现

这里我获取最大值最小值使用了stream流，下面我来介绍一下

int maxVal = Arrays.stream(arr).max().getAsInt(); 获取最大值

//Arrays.stream(arr) 将数组转换为一个流。
//max() 方法找到流中的最大值，返回一个 OptionalInt 对象。
//getAsInt() 方法从 OptionalInt 对象中获取最大值作为 int 类型的值。如果最大值不存在（即数组为空），则会抛出 NoSuchElementException 异常。文章来源地址https://www.toymoban.com/news/detail-725823.html

/*
* 基数排序实现  求相邻元素的差值(最大间距)
*
* */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class sortHomework3 {
    public static int maximumGap(int[] nums) {
        radixSort(nums);
        int r = 0;
        for (int i = 1; i < nums.length; i++) {
            r = Math.max(r,nums[i] - nums[i - 1]);
        }
        return r;
    }
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0){
            return;
        }
        int max = Arrays.stream(arr).max().getAsInt();//获得最大值,确定最高位数
        int min = Arrays.stream(arr).min().getAsInt();//获得最小值
        int digit = 1; // 从最低位开始排序
        int base = 10; // 基数为10，即十进制(是个桶)
        // 转换负数为正数
        if (min < 0) {
            max -= min;
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= min;
            }
        }
        while(max / digit > 0){
            countingSort(arr, base, digit);
            digit *= base;//处理更高位数
        }

        //排序完毕后
        // 将转换后的正数转换回负数
        if (min < 0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] += min;
            }
        }


    }

    private static void countingSort(int[] arr, int base, int digit) {
        // 定义桶的大小 (里面的泛型<表示动态数组>)为10个桶
        List<List<Integer>> buckets = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            buckets.add(new ArrayList<>()); // 创建空的桶(不创建空桶默认里面存的都是null不是桶)
        }
        for (int i : arr) {
            int index = i / digit % base;//获得位数
            buckets.get(index).add(i);//添加到集合中
        }
        int k = 0;
        //将元素在插入arr中
        for (int i = 0; i < buckets.size(); i++) {
            if (buckets.get(i).isEmpty()){
                continue;
            }
            //把各个桶中的元素存储到数组中
            for (int j = 0; j < buckets.get(i).size(); j++) {
                arr[k++] = buckets.get(i).get(j);
            }
            //取出来一个桶,咱就删除一个桶
            buckets.get(i).clear();
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8000, 3, 1};
        int[] expected = {1, 2, 3, 5, 8};
        System.out.println(Arrays.toString(arr));
        maximumGap(arr);
        System.out.println(Arrays.toString(arr));
    }
}

到了这里，关于力扣164最大间距的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！