劍指offer 面試題14―調整數組順序使奇數位于偶數前面

題目：

輸入1個整數數組，實現1個函數來調劑該數組中數組的順序，使得所有奇數位于數組的前半部份，所有偶數位于數組的后半部份。

解法1：O(n^2)

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

由于每碰到1個偶數就需要移動O(n)個數字，因此總的時間復雜度是O(n^2).

解法2：O(n)

類似快排，兩個指針，1個指向數組頭，只向后移動，1個指向數組尾，只向前移動。如果第1個指針指向的數字是偶數，并且第2個指針指向的數字是奇數，交換兩數。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈