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

相关文章

来自专栏IT可乐

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

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

2537
来自专栏Brian

C++11基础学习系列一

---- 概述 C++11标准越来越趋于稳定和成熟,国外c++11如火如荼而国内却依然处于观望期。每当提到C++很多程序员都很抵触,特别是学术界的呼声更高一些。...

2644
来自专栏机器学习算法与Python学习

“基数排序”展现Python的优雅与简洁

在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

2825
来自专栏Python入门

python循环语句详细讲解

想必大家都知道python循环语句吧,可以python循环语句有多种,比如for循环、while循环、if、else等等,

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

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

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

1183
来自专栏vue学习

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

792
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过...

3356
来自专栏积累沉淀

各种排序算法的总结和比较

1 快速排序(QuickSort) 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。...

1806
来自专栏程序员互动联盟

【编程基础】Java面向对象基础知识

前言: 前面一系列文章讲了Java的一些语法基础知识、Java中的数据类型和Java中的运算符,基本上都是学习Java语言的基础知识,从这一讲开始将会逐步介绍J...

3325
来自专栏从流域到海域

Python 函数

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

1747

扫码关注云+社区