网站建设的平台分析,建设网站如何赚钱,中国建筑出版在线官网,网站打不开了题目#xff1a;某公司有几万名员工#xff0c;请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序#xff0c;可使用O(1)的辅助空间。分析#xff1a;排序是面试时经常被提及的一类题目#xff0c;我们也熟悉其中很多种算法#xff0c;诸如插入排序、归并排序、… 题目某公司有几万名员工请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序可使用O(1)的辅助空间。分析排序是面试时经常被提及的一类题目我们也熟悉其中很多种算法诸如插入排序、归并排序、冒泡排序快速排序等等。这些排序的算法要么是O(n2)的要么是O(nlogn)的。可是这道题竟然要求是O(n)的这里面到底有什么玄机呢题目特别强调是对一个公司的员工的年龄作排序。员工的数目虽然有几万人但这几万员工的年龄却只有几十种可能。上班早的人一般也要等到将近二十岁才上班一般人再晚到了六七十岁也不得不退休。由于年龄总共只有几十种可能我们可以很方便地统计出每一个年龄里有多少名员工。举个简单的例子假设总共有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)。 转载于:https://blog.51cto.com/10541556/1831301
