LeetCode 905. Sort Array By Parity

原题链接在这里：https://leetcode.com/problems/sort-array-by-parity/description/

题目：

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 <= 5000
• 0 <= nums[i] <= 5000

题解：

Could use two pointers left from the begining and right from the end, both move to the middle and do swap when l points to odd number and right points to even number.

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int[] sortArrayByParity(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return nums;
 5         }
 6 
 7         int l = 0;
 8         int r = nums.length - 1;
 9         while(l < r){
10             while(l < r && nums[l] % 2 == 0){
11                 l++;
12             }
13 
14             while(l < r && nums[r] % 2 == 1){
15                 r--;
16             }
17 
18             if(l < r){
19                 swap(nums, l++, r--);
20             }
21         }
22 
23         return nums;
24     }
25 
26     private void swap(int[] nums, int i, int j){
27         int temp = nums[i];
28         nums[i] = nums[j];
29         nums[j] = temp;
30     }
31 }

If we want to keep the original order of even numbers, we could have both pointers moving to the same direction.

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int[] sortArrayByParity(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return nums;
 5         }
 6 
 7         int ind = 0;
 8         for(int i = 0; i < nums.length; i++){
 9             if(nums[i] % 2 == 0){
10                 swap(nums, ind++, i);
11             }
12         }
13 
14         return nums;
15     }
16 
17     private void swap(int[] nums, int i, int j){
18         int temp = nums[i];
19         nums[i] = nums[j];
20         nums[j] = temp;
21     }
22 }