实现一个排序算法，要求时间效率为O(n)
面试官：实现一个排序算法，要求时间效率为O(n)
应聘者：对什么数字，有多少个数字
面试官：对几万名公司员工的年龄
应聘者：也就是说大小在一定的范围内是吧
面试官：是的
应聘者：可以使用辅助空间吗
面试官：可以但是空间复杂度不能超过O(n)
我们遇到这个问题的思路。
- 运行使用辅助空间，可以搞一个HashTable或者数组之类的辅助
- 写代码的时候边界条件控制。第一位
- 用一个数组记录每个年龄出现的此时。然后从0到n开始遍历
- 然后从低位到高位遍历。根据当前年龄对应的次数数组，修改原来数组的排序。
废话不多说了，直接上代码。有错希望给指正~ 。
void SortAges(int ages[],int length){
//边界条件控制
if (ages == nullptr||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) {
return;
}
// 这个年龄出现的次数+1
++timesOfAge[age];
}
int index = 0;
for (int i =0 ; i<oldestAge; i++) {
// 遍历次数的数组。根据年龄。
for (int j =0 ; j<timesOfAge[i]; j++) {
ages[index] = i ;
++ index;
}
}
}
