0905. Sort Array By Parity (Easy)

Question

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1

1
2
3

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

分析/解題

給定一個不含負整數的整數陣列A，回傳一個陣列，
這個陣列的前面會是所有A的偶數的元素，
跟在後面的是所有A的奇數的元素的部分。

這題我們在先前的Move Zeros題目中有提到過類似的部分，
如果當時我們只想把0往後挪而不需考慮保留原順序，
可以從兩端開始掃描，找到左邊是0而右邊非0並交換 就可以解完此題；
這題概念是一樣的，只是變成要左邊全是偶數，右邊全是奇數 。
演算的順序大概會像這樣：

1. 分別取兩端的index作為起始(i = 0, j = l-1, l為A的長度)
2. 先確認i的位置是否為奇數，若否，則遞增i，直到A[i]為奇數
3. 再確認j的位置是否為偶數，若否，則遞減j，直到A[j]為偶數
4. 交換A[i], A[j]
5. 重複前述2~4的操作直到i不再小於j(開始前也要檢查)
6. 此時全數交換完畢，所有偶數應排在奇數之前

這邊程式碼需要注意continue的作用，
目的是讓每次index變動都進行i<j的檢查，
唯有這個條件成立，我們才有可能需要進行交換。

Java

Python的部分後面提供了一個非in-place的作法，
也就是各自將偶數和奇數的串列累積起來，
最後再將其連接。好處是比較簡單，缺點是要額外的空間來存，
端看使用者需求和題目需求來決定。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)
two pointer會掃過整個陣列，所以時間複雜度為O(N)；
如果不另外開陣列/串列的話，可以用in-place達到則空間複雜度為O(1)，
如果像Python額外提到的方法的話則由於額外儲存的關係需要O(N))

「如果除了偶數在前，奇數在後以外，要按照原先順序排列呢？」
(Python的另一個解就會按順序排)

相似及延伸：
1. ** 0283**. Move Zeros

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~