剑指offer——年龄排序问题

题目:对某公司所有员工的年龄进行排序,要求时间复杂度为O(n)

分析:

        在已有的排序算法中,性能最好的是快速排序,但是他在最好的情况下时间复杂度只能达到O(nlogn),无法满足本题的要求。但是我们可以从“年龄”这一特殊条件入手。

        年龄具有显著的特征,那就是这些数值都分布在0-99之间。由于待排序的数值均在0-99这个固定区间内,因此我们可以用一个长度为100的数组,记录0-99这100个年龄出现的次数。我们只需要扫描一遍所有员工的年龄,就能统计出这个数组。最后只需要将该数组展开即可获得想要的结果。

/**
 * 对某公司所有员工的年龄进行排序,要求时间复杂度为O(n)
 * @author chibozhou
 *
 */
public class AgeSort {
	/**
	 * 排序函数
	 * @param ages 存放公司全体人员年龄的数组
	 */
	public static void ageSort(int[] ages){
		//countAge的下标i代表年龄,countAge[i]代表年龄为i的员工人数
		int[] countAge = new int[100];
		
		//健壮性判断
		if(ages==null || ages.length<=0){
			System.out.println("数组为空!");
			return;
		}
		for(int i=0;i<ages.length;i++){
			if(ages[i]<0 || ages[i]>99){
				System.out.println("数组中存在非法年龄!");
				return;
			}
		}
		
		//统计每个年龄的人数,存储在countAge数组中
		for(int i=0;i<ages.length;i++)
			countAge[ages[i]]++;
		
		//将countAge数组展开,存放在ages数组中
		int curIndex = 0;//用于记录ages数组当前下标
		for(int i=0;i<countAge.length;i++){
			for(int j=0;j<countAge[i];j++){
				ages[curIndex] = i;
				curIndex++;
			}
		}
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏眯眯眼猫头鹰的小树杈

leetcode349. Intersection of Two Arrays

思路一模仿了归并排序的merge部分。先将两个数组分别排序,排序完成之后再用两个指针分别比较两个数组的值。如果两个指针指向的值相同,则向结果集中添加该元素并且同...

773
来自专栏PHP技术

正则表达式详解

点号(.)是元字符,匹配除换行符以外的任意字符。 星号(*)是元字符,代表数量。 点号星号连在一起就是匹配任意数量的不包括换行符的字符。 \s匹配任意空白字符。...

2725
来自专栏数据结构与算法

1216 跳马问题

1216 跳马问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 题目 ? ...

2565
来自专栏决胜机器学习

有趣的算法(七) ——快速排序改进算法

有趣的算法(七) ——快速排序改进算法 (原创内容,转载请注明来源,谢谢) 一、概述 快速排序,被认为是最好的排序算法之一。快速排序是20世纪60年代被提出...

3034
来自专栏代码世界

Python基础数据类型之int、bool、str

数据类型:int  bool  str  list  元祖  dict  集合 int:整数型,用于各种数学运算。 bool:只有两种,True和False,用...

3166
来自专栏猿人谷

三位数的排列组合

题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列...

1949
来自专栏数据结构与算法

4906 删数问题

4906 删数问题  时间限制: 1 s  空间限制: 2000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description   键盘输入一个...

2495
来自专栏软件开发

C语言 经典编程100题

一、题目 【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? ===========================...

2527
来自专栏web前端教室

javascript数据结构之基数排序浅淡

队列是一种列表,但它只能在队头删除元素,并在队尾插入元素。 所以,它是一个有序的列表,是先进先出的。 就像在银行排除一样,先到先办,新人排在后面。 可以使用队列...

1899
来自专栏前端儿

表达式求值(1)

Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值...

792

扫码关注云+社区