實(shí)現(xiàn)一個(gè)排序算法，要求時(shí)間效率為O(n)
面試官：實(shí)現(xiàn)一個(gè)排序算法，要求時(shí)間效率為O(n)
應(yīng)聘者：對(duì)什么數(shù)字，有多少個(gè)數(shù)字
面試官：對(duì)幾萬(wàn)名公司員工的年齡
應(yīng)聘者：也就是說(shuō)大小在一定的范圍內(nèi)是吧
面試官：是的
應(yīng)聘者：可以使用輔助空間嗎
面試官：可以但是空間復(fù)雜度不能超過(guò)O(n)
我們遇到這個(gè)問(wèn)題的思路渐苏。
- 運(yùn)行使用輔助空間，可以搞一個(gè)HashTable或者數(shù)組之類的輔助
- 寫代碼的時(shí)候邊界條件控制菇夸。第一位
- 用一個(gè)數(shù)組記錄每個(gè)年齡出現(xiàn)的此時(shí)琼富。然后從0到n開(kāi)始遍歷
- 然后從低位到高位遍歷。根據(jù)當(dāng)前年齡對(duì)應(yīng)的次數(shù)數(shù)組庄新，修改原來(lái)數(shù)組的排序鞠眉。
廢話不多說(shuō)了，直接上代碼择诈。有錯(cuò)希望給指正~ 械蹋。
void SortAges(int ages[],int length){
//邊界條件控制
if (ages == nullptr||length<=0) {
return;
}
const int oldestAge = 99 ;
//記錄每個(gè)年齡出現(xiàn)的次數(shù)
int timesOfAge[oldestAge+1];
//初始化數(shù)組
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;
}
// 這個(gè)年齡出現(xiàn)的次數(shù)+1
++timesOfAge[age];
}
int index = 0;
for (int i =0 ; i<oldestAge; i++) {
// 遍歷次數(shù)的數(shù)組。根據(jù)年齡羞芍。
for (int j =0 ; j<timesOfAge[i]; j++) {
ages[index] = i ;
++ index;
}
}
}
