面试算法:数组相对排序
2023-12-28 14:14:10
题目
计数排序是一种线性时间的整数排序算法。如果数组的长度为n,整数范围(数组中最大整数与最小整数的差值)为k,对于k远小于n的场景(如对某公司所有员工的年龄排序),那么计数排序的时间复杂度优于其他基于比较的排序算法(如归并排序、快速排序等)。
分析
计数排序的基本思想是先统计数组中每个整数在数组中出现的次数,然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。例如,如果输入整数数组[2,3,4,2,3,2,1],扫描一次整个数组就能知道数组中1出现了1次,2出现了3次,3出现了2次,4出现了1次,于是先后在数组中填入1个1、3个2、2个3及1个4,就可以得到排序后的数组[1,2,2,2,3,3,4]。
解
public class Test {
public static void main(String[] args) {
int[] nums = {2, 3, 4, 2, 3, 2, 1};
int[] result = sortArray(nums);
for (int item : result) {
System.out.println(item);
}
}
public static int[] sortArray(int[] nums) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}
int[] counts = new int[max - min + 1];
for (int num : nums) {
counts[num - min]++;
}
int i = 0;
for (int num = min; num <= max; num++) {
while (counts[num - min] > 0) {
nums[i++] = num;
counts[num - min]--;
}
}
return nums;
}
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135266118
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!