劍指offer 面試題14―調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

題目：

輸入1個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)1個(gè)函數(shù)來(lái)調(diào)劑該數(shù)組中數(shù)組的順序，使得所有奇數(shù)位于數(shù)組的前半部份，所有偶數(shù)位于數(shù)組的后半部份。

解法1：O(n^2)

從頭掃描數(shù)組，每碰到1個(gè)偶數(shù)，拿出這個(gè)數(shù)字，并把位于這個(gè)數(shù)字后面的所有數(shù)字往前移動(dòng)1位。挪完以后在數(shù)組的末尾有1個(gè)空位，這時(shí)候把該偶數(shù)放入這個(gè)空位中。

由于每碰到1個(gè)偶數(shù)就需要移動(dòng)O(n)個(gè)數(shù)字，因此總的時(shí)間復(fù)雜度是O(n^2).

解法2：O(n)

類(lèi)似快排，兩個(gè)指針，1個(gè)指向數(shù)組頭，只向后移動(dòng)，1個(gè)指向數(shù)組尾，只向前移動(dòng)。如果第1個(gè)指針指向的數(shù)字是偶數(shù)，并且第2個(gè)指針指向的數(shù)字是奇數(shù)，交換兩數(shù)。

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)