首页 > 代码库 > 【剑指offer】员工年龄排序
【剑指offer】员工年龄排序
典型的以空间换时间问题,思路很重要!
/* 员工年龄排序 员工可能有几万名,要求时间复杂度为O(n) 思路:员工的年龄必然在一个范围内,比如0-99,那么我们建立一个大小为100的辅助数组,然后遍历 员工年龄,取到一个年龄就将该年龄对应数组位置的值加1,最终数组中便保存了不同年龄的员工的个数 最后,打印数组即可。 by Rowandjj 2014/7/22 */ #include<iostream> using namespace std; #define MAX 100 void sort(int ages[],int len) { int temp[MAX],i,j; //初始化辅助数组 for(i = 0; i < MAX; i++) { temp[i] = 0; } //遍历年龄数组,获取不同年龄的员工个数存到辅助数组中 for(i = 0;i < len; i++) { temp[ages[i]]++; } //对年龄数组排序 int index = 0; for(i = 0; i < MAX; i++) { for(j = 0; j < temp[i]; j++) { ages[index] = i; index++; } } } int main() { int ages[] = {21,56,13,23,11,21,6,12,13,53,11,56,12,13,5,11,45,11,41,67,21,56,23,19,10}; sort(ages,25); for(int i = 0; i < 25; i++) { cout<<ages[i]<<" "; } cout<<endl; return 0; }
测试:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。