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

相关文章

来自专栏黑泽君的专栏

Java语言中:在数据类型的讲解中补充的几个小问题

============================================================================= 1...

691
来自专栏IT可乐

Java数据结构和算法(七)——链表

  前面博客我们在讲解数组中,知道数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且...

3267
来自专栏java思维导图

【一分钟知识】面对对象、基本类型

【一分钟回顾】系列 很多知识都是概念性的东西,有时候你知道这个技术的用法,但未必就能准确地说出它代表的含义与思想。一分钟回顾系列文章会从基础开始到后期的高级,带...

2875
来自专栏从零开始学 Web 前端

js变量提升与函数提升的详细过程

在这里我会从 Web 前端零基础开始,一步步学习 Web 相关的知识点,期间也会分享一些好玩的项目。现在就让我们一起进入 Web 前端学习的冒险之旅吧!

1583
来自专栏从流域到海域

Python 函数

Python的函数与其他语言的函数概念上是一致的,只是形式上有所不同。在面向过程的编程语言中(C语言),函数是代码的基本组成形式,是功能的基本模块;在面向...

1887
来自专栏开源优测

Python3快速排序

Python3快速排序 概述 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。 通过一趟排序将要...

3726
来自专栏chenjx85的技术专栏

leetcode-561-Array Partition I

1867
来自专栏菩提树下的杨过

as3:Function以及call,apply

Function类在as3中是直接从Object继承下来的,通常开发者定义的每一个function,均可以认为是Function类的一个实例。  如果硬要跟c#...

1859
来自专栏vue学习

JS数据结构与算法-快速排序与二分查找算法

932
来自专栏算法channel

LeetCode实战:子问题分析

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 记...

3479

扫码关注云+社区