首页 > 代码库 > 53. 特殊的O(n)时间排序[sort ages with hashtable]

53. 特殊的O(n)时间排序[sort ages with hashtable]

2024-07-05 22:47:34   221人阅读

【本文链接】

http://www.cnblogs.com/hellogiser/p/sort-ages-with-hashtable.html

【题目】

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

【分析】

排序是面试时经常被提及的一类题目，我们也熟悉其中很多种算法，诸如插入排序、归并排序、冒泡排序，快速排序等等。这些排序的算法，要么是O(n2)的，要么是O(nlogn)的。可是这道题竟然要求是O(n)的，这里面到底有什么玄机呢？

题目特别强调是对一个公司的员工的年龄作排序。员工的数目虽然有几万人，但这几万员工的年龄却只有几十种可能，因此想到可以通过使用Hash表来辅助排序。由于年龄总共只有几十种可能，我们可以很方便地统计出每一个年龄里有多少名员工。举个简单的例子，假设总共有5个员工，他们的年龄分别是25、24、26、24、25。我们统计出他们的年龄，24岁的有两个，25岁的也有两个，26岁的一个。那么我们根据年龄排序的结果就是：24、24、25、25、26，即在表示年龄的数组里写出两个24、两个25和一个26。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
  
// 53_SortAges.cpp : Defines the entry point for the console application.
//
/*
     version: 1.0
     author: hellogiser
     blog: http://www.cnblogs.com/hellogiser
     date: 2014/5/24
*/

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;
#define MAX 10
#define OLDEST 99

int ages[MAX];

// init ages
void InitAges(int *ages, int n)
{
     srand(time(NULL));
    for (int i = 0; i < n; ++i)
         ages[i] = rand() % 100;
}

// print ages
void PrintAges(int *ages, int n)
{
    if(NULL == ages || n <= 0)
        return;
    for (int i = 0; i < n; ++i)
         printf("%d ", ages[i]);
     printf("\n");
}

// sort ages in O(n)
void SortAges(int *ages, int n)
{
    if(NULL == ages || n <= 0)
        return;
    int timesOfAge[OLDEST + 1];
    // init times to 0
    for(int i = 0; i <= OLDEST; ++i)
         timesOfAge[i] = 0;

    // get age times
    for (int i = 0; i < n; ++i)
     {
        int age = ages[i];
        if(age <= 0 || age > 100)
            throw new std::exception("age out of range!");
         ++timesOfAge[age];
     }

    // sort ages by times
    int index = 0;
    for (int i = 0; i <= OLDEST; ++i)
        for(int j = 0; j < timesOfAge[i]; ++j)
         {
             ages[index] = i;
             ++index;
         }
}

void test_case()
{
     InitAges(ages, MAX);
     PrintAges(ages, MAX);
     SortAges(ages, MAX);
     PrintAges(ages, MAX);
}

int _tmain(int argc, _TCHAR *argv[])
{
     test_case();
    return 0;
}
/*
79 61 74 76 64 1 28 31 31 79
1 28 31 31 61 64 74 76 79 79
*/

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

【参考】

http://zhedahht.blog.163.com/blog/static/25411174201131184017844/

http://blog.csdn.net/sunmeng_007/article/details/8047338

【本文链接】

http://www.cnblogs.com/hellogiser/p/sort-ages-with-hashtable.html


联系
我们