剑指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 条评论
登录 后参与评论

相关文章

来自专栏web前端教室

javascript 红皮高程(17)-- 按位异或(XOR)

不吐槽了,继续研究JS,今天是按位异或这个操作符,它用符号(^)表示,它也是有二个操作数,这二个数当然也是十进制转成二进制之后的数。 它的规则就是,二个数的数值...

1686
来自专栏点滴积累

python通过一个语句分析几个常用函数和概念

前言 过年也没完全闲着,每天用一点点时间学点东西,本文为大家介绍几个python操作的细节,包含all、any、for in等操作,以及介绍我解决问题的思路。 ...

2595
来自专栏CodeSheep的技术分享

Java编程思想学习录(连载之:内部类)

19611
来自专栏PHP技术

5个值得深思的 PHP 面试问题

文章所罗列的问题虽然看似简单,但是每个背后都涵盖了一个或几个大家容易忽视的基础知识点,希望能够帮助到你的面试和平时工作。 Q1 ? 正确运行的输出结果: "y...

2814
来自专栏西安-晁州

js中的深浅拷贝

js中的深浅拷贝 js中有深拷贝、浅拷贝一说,所谓的深浅拷贝是针对value类型为引用类型(函数、对象、数组)而言的,大概理解的就是: 浅拷贝: 拷贝出...

3195
来自专栏GreenLeaves

正则表达式简介

简介:完整的正则表达式由两种字符构成。特殊字符(如*、[]、&、@、$等称为元字符),其他为文字,或者是普通字符,为了便于理解,我们可以把正则表达式想象为普通的...

1916
来自专栏vue学习

函数声明提升与变量提升

1.当在函数的作用域里定义一个和外部变量一样的名称的变量时,变量声明会提升至第一句,但是赋值则不变

632
来自专栏Python小屋

Python中的偏函数和函数柯里化

偏函数(partial)和函数柯里化(currying)是函数式编程中常用的技术。有时候我们在复用已有函数时可能需要固定其中的部分参数,这除了可以通过默认值参数...

2544
来自专栏黑白安全

PHP常量介绍

​变量和常量是计算机编程中的一个重要概念,变量或常量可以理解为是程序给一些数据取得名字,编程时,因为一些数据随着程序的运行而改变,所以不能直接使用这些数据,需要...

733
来自专栏林德熙的博客

dotnet 设计规范 · 结构体定义

易变的属性指的是在调用属性返回值的时候返回的是新的实例,易变的属性会有很多的问题。

391

扫描关注云+社区