力扣164最大间距

1.前言

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

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

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

2.思路分析

1. 首先，找到待排序数组中的最大值，确定最大值的位数。假设最大值是max，位数是d。

2. 创建10个桶（0-9），每个桶用来存放对应位数上的数字。

3. 从低位（个位）开始，根据当前位数的值将待排序数组中的数字放入对应的桶中。

4. 将桶中的数字按照顺序取出，覆盖原数组，然后进入下一位数的排序。

5. 重复步骤3和步骤4，直到排完最高位（即 d 位）。

6. 最后，遍历排序后的数组，计算相邻数字之间的差值，找到最大的差值，即为最大间距。

3.代码实现 

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

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

//Arrays.stream(arr) 将数组转换为一个流。
//max() 方法找到流中的最大值，返回一个 OptionalInt 对象。
//getAsInt() 方法从 OptionalInt 对象中获取最大值作为 int 类型的值。如果最大值不存在（即数组为空），则会抛出 NoSuchElementException 异常。

/*
* 基数排序实现  求相邻元素的差值(最大间距)
*
* */
 
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> 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));
    }
}