LintCode 373: Partition Array

題目描述

分割一個整數數組，使得奇數在前偶數在后。

樣例

給定[1, 2, 3, 4]，返回[1, 3, 2, 4]。

Thu Feb 23 2017

思路

簡單題，可以很自然地想到再用一個答案數組，從頭到尾遍歷一遍，遇到奇數就放到答案數組的前面，遇到偶數就放到答案數組的后面。

還有另一種方法，跟快速排序的形式有點像，即從前面找到一個偶數，同時從后面找到一個奇數，將兩個數調換。

雖然兩種方法的時間復雜度都是\(O(n)\)，但是第二種方法的空間復雜度是\(O(1)\)，算是更優的方法。

代碼

// 奇偶分割數組 void partitionArray(vector<int> &nums) {if (nums.size() <= 0) return;vector<int>::iterator l = nums.begin(), r = nums.end() - 1;while(l != r){while (l != r && *l % 2 == 1) ++l;while (l != r && *r % 2 == 0) --r;swap(*l, *r);} }

轉載于:https://www.cnblogs.com/genkun/p/6436058.html

總結

以上是生活随笔為你收集整理的LintCode 373: Partition Array的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。