O(n)时间的排序

题目:某公司有几万名员工,请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序,可使用O(1)的辅助空间。

     题目特别强调是对一个公司的员工的年龄作排序。员工的数目虽然有几万人,但这几万员工的年龄却只有几十种可能。上班早的人一般也要等到将近二十岁才上班,一般人再晚到了六七十岁也不得不退休。

由于年龄总共只有几十种可能,我们可以很方便地统计出每一个年龄里有多少名员工。举个简单的例子,假设总共有5个员工,他们的年龄分别是25、24、26、24、25。我们统计出他们的年龄,24岁的有两个,25岁的也有两个,26岁的一个。那么我们根据年龄排序的结果就是:24、24、25、25、26,即在表示年龄的数组里写出两个24、两个25和一个26。

想明白了这种思路,我们就可以写出如下代码:

void SortAges(int ages[], int length)
{
    if(ages == NULL || length <= 0)
        return;

    const int oldestAge = 99;
    int timesOfAge[oldestAge + 1];

    for(int i = 0; i <= oldestAge; ++ i)
        timesOfAge[i] = 0;

    for(int i = 0; i < length; ++ i)
    {
        int age = ages[i];
        if(age < 0 || age > oldestAge)
            throw new std::exception("age out of range.");

        ++ timesOfAge[age];
    }

    int index = 0;
    for(int i = 0; i <= oldestAge; ++ i)
    {
        for(int j = 0; j < timesOfAge[i]; ++ j)
        {
            ages[index] = i;
            ++ index;
        }
    }
}

在上面的代码中,允许的范围是0到99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次,就在数组ages里设置几次该年龄。这样就相当于给数组ages排序了。该方法用长度100的整数数组辅助空间换来了O(n)的时间效率。由于不管对多少人的年龄作排序,辅助数组的长度是固定的100个整数,因此它的空间复杂度是个常数,即O(1)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人随笔

Java 关于接口的那点事儿

接口的应用 接口是一种能力 关键字:interface 语法:  public interface MyInterface{   public void ...

40980
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

我们应该如何对事物进行比较和排序?这问题听上去有点莫名其妙,但我希望你认真考虑一下。比方说,我们有一组苹果:

6510
来自专栏醒者呆

融会贯通——最常用的面向对象设计原则“合成复用原则”

复用一个类的时候,多使用对象的组合/聚合的关联关系,而不是继承。 之前提到的“依赖倒转原则”,是以里氏代换原则为基础的实现开闭原则目标的手段,这一条路线涉及到的...

31680
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

还有一个不错的视频(https://marcus-biel.com/java-comparable-interface-video-tutorial/)。

11850
来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

34180
来自专栏懒人开发

(2.5)James Stewart Calculus 5th Edition: Continuity

如果在一个区间中,不包括a, 则在 a点不连续(f is discontinuous at a)

11640
来自专栏Python爱好者

Python高效编程(二)

15540
来自专栏趣谈编程

归并排序

面试官: 聊聊归并排序 归并排序是建立在归并操作的一种高效的排序方法,该方法采用了分治的思想,比较适用于处理较大规模的数据,但比较耗内存,今天我们聊聊归并排序 ...

42370
来自专栏CodingToDie

Python学习(八):类和对象 以另一种思维看待世界

第8 章 类和对象 以另一种思维看待世界 对世界万物的状态与行为进行归纳与分类,以此分析个体与个体间的相互作用与影响方法。 Table of Contents ...

39370
来自专栏技术之路

设计模式:抽象工厂方法模式

今天说一下抽象工厂模式:提供一个接口,用于创建相关或依赖对象的家族,而不需要明确指定具体类。 抽象工厂允许客户使用抽象的接口来创建一组相关的产品,而不需要知道实...

21650

扫码关注云+社区

领取腾讯云代金券