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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

Example 1:

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

 Idea 1. Borrow the partition idea from quicksort, like Dutch flag problem, assume the array is already sorted as required, what to do with new element?

even | odd | ?

Time complexity: O(n)

Space complexity: O(1)

 1 class Solution {
 2     private void swap(int[] A, int i, int j) {
 3         int a = A[i];
 4         A[i] = A[j];
 5         A[j] = a;
 6     }
 7     
 8     public int[] sortArrayByParity(int[] A) {
 9         int evenEnd = -1;
10         for(int i = 0; i < A.length; ++i) {
11             if(A[i]%2 == 0) {
12                 ++evenEnd;
13                 swap(A, evenEnd, i);
14             }
15         }
16         return A;
17     }
18 }

Idea 1.a Two pointers walking toward each other and swap if not in the right place

 1 class Solution {
 2     private void swap(int[] A, int i, int j) {
 3         int a = A[i];
 4         A[i] = A[j];
 5         A[j] = a;
 6     }
 7     
 8     public int[] sortArrayByParity(int[] A) {
 9        for(int left = 0, right = A.length-1; left < right; ) {
10            while(left < right && A[left]%2 == 0) {
11                ++left;
12            }
13            
14            while(left < right && A[right]%2 == 1) {
15                --right;
16            }
17            
18            if(left < right) {
19                swap(A, left, right);
20                ++left;
21                --right;
22            }
23        }
24         return A;
25     }
26 }

slightly more cleaner 

 1 class Solution {
 2     private void swap(int[] A, int i, int j) {
 3         int a = A[i];
 4         A[i] = A[j];
 5         A[j] = a;
 6     }
 7     
 8     public int[] sortArrayByParity(int[] A) {
 9        for(int left = 0, right = A.length-1; left < right; ) {
10           if(A[left]%2 == 1 && A[right]%2 == 0) {
11               swap(A, left, right);
12           }
13            
14           if(A[left]%2 == 0) {
15               ++left;
16           }
17            
18           if(A[right]%2 == 1) {
19               --right;
20           }
21        }
22         return A;
23     }
24 }

Idea 2. customised comparator to sort

Time complexity: O(nlogn)

Space complexity: O(n)

 1 class Solution {
 2     public int[] sortArrayByParity(int[] A) {
 3        
 4         Integer[] B = new Integer[A.length];
 5         for(int i = 0; i < A.length; ++i) {
 6             B[i] = A[i];
 7         }
 8         
 9         Comparator<Integer> cmp = (a, b) -> Integer.compare(a%2, b%2);
10         Arrays.sort(B, cmp);
11         
12         for(int i = 0; i < A.length; ++i) {
13             A[i] = B[i];
14         }
15         
16         return A;
17     }
18 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄