抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

年龄排序问题

题:

解题思路:

公司员工的年龄有一个范围。允许的范围是0~99岁。
数组timesOfAge 用来统计每个年龄出现的次数。某个年龄出现了多少次,
就在数组ages 里设置几次该年龄,这就相当于给数组ages 排序了。
该方法用长度100的整数数组作为辅助空间换来了O(n)的时间效率。

代码:

private static void sortAge(int[] ages, int length) throws Exception {
if (ages == null || length <= 0) {
return;
}
//定义一个最大年龄
int oldestAge = 99;
//定义一个与年龄等长的数组用于记录某个年龄所出现的次数
int[] timeOfAge = new int[oldestAge + 1];
//将每个年龄出现的次数都置零
for (int i = 0; i < oldestAge; i++) {
timeOfAge[i] = 0;
}
//循环ages数组 对每次出现的年龄计数
for (int i = 0; i < length; i++) {
int age = ages[i];
if (age < 0 || age > oldestAge) {
throw new Exception("age out of range");
}
++timeOfAge[age];
}
//至此 timeOfAge数组的index为年龄 值为出现的次数
int index = 0;
for (int i = 0; i < oldestAge; i++) {
//0开始到从最大年龄进行遍历
//年龄未出现过 则timeOfAge[i]=0,理解时将i换成age就比较好理解了
for (int j = 0; j < timeOfAge[i]; j++) {
//重新赋值给ages数组 如果多次出现 则将index+1,移至下一位继续赋值
ages[index] = i;
++index;
}
}

}

这是一个比较明显的以空间换时间的解法。


0条评论

发表评论