网站制作方案设计,怎样自创广告网站,怎么做可以使网站跳转,怎么搞自己的网站1.前言 因为昨天写了一个基数排序#xff0c;今天我来写一道用基数排序实现的题解#xff0c;希望可以帮助你理解基数排序。
这个题本身不难#xff0c;就是线性时间和线性额外空间(O(n))的算法#xff0c;有点难实现 基数排序的时间复杂度是O(d*(nradix))#xff0c;其中…1.前言 因为昨天写了一个基数排序今天我来写一道用基数排序实现的题解希望可以帮助你理解基数排序。
这个题本身不难就是线性时间和线性额外空间(O(n))的算法有点难实现 基数排序的时间复杂度是O(d*(nradix))其中d是最大值的位数n是数组长度radix是基数10然后化简就是 O(n) 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 异常。 /*
* 基数排序实现 求相邻元素的差值(最大间距)
*
* */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个桶ListListInteger 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));}
}
