重庆长寿网站设计公司哪家好,优秀个人网站模板,个人网站多少钱,做电商哪个设计网站比较好概念#xff1a;
计数排序#xff08;Counting sort#xff09;是一个非基于比较稳定的线性时间的排序算法
非基于比较#xff1a;之前学的排序都是通过比较数据的大小来实现有序的#xff0c;比如希尔排序等#xff0c;而计数排序不需要比较数据的大小而进行排序…概念
计数排序Counting sort是一个非基于比较稳定的线性时间的排序算法
非基于比较之前学的排序都是通过比较数据的大小来实现有序的比如希尔排序等而计数排序不需要比较数据的大小而进行排序计数排序顾名思义就是根据计数进行排序
工作原理使用一个额外的数组arr,其中第i个元素是待排序数组A中值等于i的元素的个数然后根据数组arr来将A中的元素排到正确的位置上 具体实现创建一个足够大的数组arr,足够大的意思是arr的下标范围可以包括所有的待排序数据值然后遍历待排序数据使用计数法统计每个数据出现的次数最后遍历arr数组将每一个值arr[i]的下标i放入arr[i]次
// 计数排序// 求数组中元素的最大值private int getMaxVal(int[] arr) {return Arrays.stream(arr).max().getAsInt();}public void countSort(int[] arr) {// 对数组进行判断if (arr null || arr.length 2) {return;}// 获取数组中最大值int max getMaxVal(arr);// 创建一个比max多1个元素的数组int[] c new int[max 1];// 统计Arrays.stream(arr).forEach(item - c[item]);// 数组回填int index 0;for (int i 0; i c.length; i) {while (c[i] 0) {arr[index] i;c[i]--;}}} 计数排序的排序是不是和数组的索引有关索引是0,所以是不是我们如果碰到数列中有负数的情况计数排序就失效了呢一般的计数排序确实是失效了但是咋们是二班的技术排序
上离散化技术排序 // 离散化计数排序public void countSort2(int[] arr) {// 去重排序---形成离散化之后的数组int[] s Arrays.stream(arr).distinct().sorted().toArray();// 创建一个统计数组int[] c new int[s.length];// 进行统计// 从s数组中找arr[i]对应的索引Arrays.stream(arr).forEach(item - {int index find(s, item, 0, s.length - 1);c[index];});// 回填int index 0;for (int i 0; i c.length; i) {while (c[i] 0) {arr[index] s[i];c[i]--;}}}// 二分查找法private int find(int[] arr, int num, int left, int right) {// 先找中间值while (left right) {int mid left (right - left) / 2;if (arr[mid] num) {return mid;} else if (arr[mid] num) {right mid - 1;} else {left mid 1;}}return -1;} leetcode题单
找不同
class Solution {public char findTheDifference(String s, String t) {if (s null t null) {return 0;}int[] hash new int[256];for (int i 0; i s.length(); i) {hash[s.charAt(i)];}for (int i 0; i t.length(); i) {hash[t.charAt(i)];}for (int i 0; i hash.length; i) {if((hash[i]1)1){return (char) (i);}}return 0;}
}
既不是最小值也不是最大值
class Solution {public int findNonMinOrMax(int[] nums) {if (nums.length 3) return -1;countSort(nums); // 只对前三个数排序return nums[1];}public void countSort(int[] arr) {// 对数组进行判断if (arr null || arr.length 2) {return;}// 获取数组中最大值int max getMaxVal(arr);// 创建一个比max多1个元素的数组int[] c new int[max 1];// 统计Arrays.stream(arr).forEach(item - c[item]);// 数组回填int index 0;for (int i 0; i c.length; i) {while (c[i] 0) {arr[index] i;c[i]--;}}}private int getMaxVal(int[] arr) {return Arrays.stream(arr).max().getAsInt();}}
