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

相关文章

来自专栏JavaEdge

2018-09-04Q:求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。方法一:递归实现1+2+..+n;

共同点:一,利用利用短路 && 来实现 if的功能;二,利用递归来实现循环while的功能

982
来自专栏积累沉淀

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

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

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

【答疑解惑】C语言里面如何计算数据类型取值范围?

先看一个网友的问题: ? 初学者有不少会对数据类型的取值范围有疑问,数据类型的取值范围关系到定义合适的变量,尤其是在进行嵌入式开发时更要清楚。这里有必要介绍一下...

3816
来自专栏IT可乐

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

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

4287
来自专栏chenjx85的技术专栏

leetcode-561-Array Partition I

1937
来自专栏黑泽君的专栏

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

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

831
来自专栏开源优测

Python3快速排序

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

4146
来自专栏vue学习

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

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

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

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

2383
来自专栏从流域到海域

Python 函数

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

2107

扫码关注云+社区

领取腾讯云代金券