題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。

分析：如果不考慮時(shí)間復(fù)雜度，最簡(jiǎn)單的思路應(yīng)該是從頭掃描這個(gè)數(shù)組，每碰到一個(gè)偶數(shù)時(shí)，拿出這個(gè)數(shù)字，并把位于這個(gè)數(shù)字后面的所有數(shù)字往前挪動(dòng)一位。挪完之后在數(shù)組的末尾有一個(gè)空位，這時(shí)把該偶數(shù)放入這個(gè)空位。由于碰到一個(gè)偶數(shù)，需要移動(dòng)O(n)個(gè)數(shù)字，因此總的時(shí)間復(fù)雜度是O(n^２)。

要求的是把奇數(shù)放在數(shù)組的前半部分，偶數(shù)放在數(shù)組的后半部分，因此所有的奇數(shù)應(yīng)該位于偶數(shù)的前面。也就是說(shuō)我們?cè)趻呙柽@個(gè)數(shù)組的時(shí)候，如果發(fā)現(xiàn)有偶數(shù)出現(xiàn)在奇數(shù)的前面，我們可以交換他們的順序，交換之后就符合要求了。

因此我們可以維護(hù)兩個(gè)指針，第一個(gè)指針初始化為數(shù)組的第一個(gè)數(shù)字，它只向后移動(dòng)；第二個(gè)指針初始化為數(shù)組的最后一個(gè)數(shù)字，它只向前移動(dòng)。在兩個(gè)指針相遇之前，第一個(gè)指針總是位于第二個(gè)指針的前面。如果第一個(gè)指針指向的數(shù)字是偶數(shù)而第二個(gè)指針指向的數(shù)字是奇數(shù)，我們就交換這兩個(gè)數(shù)字。

基于這個(gè)思路，我們可以寫出如下的代碼：

void Reorder(int *pData, unsigned int length, bool (*func)(int)); bool isEven(int n);/ // Devide an array of integers into two parts, odd in the first part, // and even in the second part // Input: pData - an array of integers // length - the length of array / void ReorderOddEven(int *pData, unsigned int length) {if(pData == NULL || length == 0)return;Reorder(pData, length, isEven); }/ // Devide an array of integers into two parts, the intergers which // satisfy func in the first part, otherwise in the second part // Input: pData - an array of integers // length - the length of array // func - a function / void Reorder(int *pData, unsigned int length, bool (*func)(int)) {if(pData == NULL || length == 0)return;int *pBegin = pData;int *pEnd = pData + length - 1;while(pBegin < pEnd){// if *pBegin does not satisfy func, move forwardif(!func(*pBegin)){pBegin ++;continue;}// if *pEnd does not satisfy func, move backwardif(func(*pEnd)){pEnd --;continue;}// if *pBegin satisfy func while *pEnd does not,// swap these integersint temp = *pBegin;*pBegin = *pEnd;*pEnd = temp;} }/ // Determine whether an integer is even or not // Input: an integer // otherwise return false / bool isEven(int n) {return (n & 1) == 0; }

討論：

上面的代碼有三點(diǎn)值得提出來(lái)和大家討論：

１．函數(shù)isEven判斷一個(gè)數(shù)字是不是偶數(shù)并沒有用%運(yùn)算符而是用&。理由是通常情況下位運(yùn)算符比%要快一些；

２．這道題有很多變種。這里要求是把奇數(shù)放在偶數(shù)的前面，如果把要求改成：把負(fù)數(shù)放在非負(fù)數(shù)的前面等，思路都是都一樣的。

３．在函數(shù)Reorder中，用函數(shù)指針func指向的函數(shù)來(lái)判斷一個(gè)數(shù)字是不是符合給定的條件，而不是用在代碼直接判斷（hard code）。這樣的好處是把調(diào)整順序的算法和調(diào)整的標(biāo)準(zhǔn)分開了（即解耦，decouple）。當(dāng)調(diào)整的標(biāo)準(zhǔn)改變時(shí)，Reorder的代碼不需要修改，只需要提供一個(gè)新的確定調(diào)整標(biāo)準(zhǔn)的函數(shù)即可，提高了代碼的可維護(hù)性。例如要求把負(fù)數(shù)放在非負(fù)數(shù)的前面，我們不需要修改Reorder的代碼，只需添加一個(gè)函數(shù)來(lái)判斷整數(shù)是不是非負(fù)數(shù)。這樣的思路在很多庫(kù)中都有廣泛的應(yīng)用，比如在ＳＴＬ的很多算法函數(shù)中都有一個(gè)仿函數(shù)（functor）的參數(shù)（當(dāng)然仿函數(shù)不是函數(shù)指針，但其思想是一樣的）。如果在面試中能夠想到這一層，無(wú)疑能給面試官留下很好的印象。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動(dòng)，書中的分析講解更加詳細(xì)。歡迎關(guān)注。

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(29)-调整数组顺序使奇数位于偶数前面[算法]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。