Last Updated on 2022-05-02 by Clay
題目
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
Example 1:
Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Example 2:
Input: nums = [0] Output: [0]
Constraints:
1 <= nums.length <= 50000 <= nums[i] <= 5000
題目給定一組數值陣列，我們要將偶數放在前方、而奇數放在後方。偶數之間可以任意順序、奇數間同樣也可以任意順序。
解題思路
兩端點解法
我的想法很簡單，就是同時判斷陣列的左右兩端。
如果左方的位置為奇數、而右方為偶數，則兩兩交換。接著左方加一、右方減一。
如果左方是偶數，則繼續加一，因為我們要找到左方為奇數的。
如果右方是奇數，則繼續減一，因為我們要找到右方為偶數的。
最後在左方跟右方重疊時，結束尋找。
如此一來，我們的陣列就會是偶數全部在前方而奇數全部在後方了。
兩端點解法複雜度
| Time complexity | O(n) |
| Space complexity | O(1) |
兩端點解法 C++ 範例程式碼
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
// Init
int l = 0;
int r = nums.size() - 1;
// Two point
while (l < r) {
if (nums[l] % 2 == 1 && nums[r] % 2 == 0) {
swap(nums[l], nums[r]);
++l;
--r;
}
if (nums[l] % 2 == 0) ++l;
if (nums[r] % 2 == 1) --r;
}
return nums;
}
};兩端點解法 Python 範例程式碼
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
# Init
l = 0
r = len(nums) - 1
# Two point
while l < r:
if nums[l] % 2 == 1 and nums[r] % 2 == 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
if nums[l] % 2 == 0: l += 1
if nums[r] % 2 == 1: r -= 1
return nums