来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-array-by-parity/

描述

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。

示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示：
1 <= A.length <= 5000
0 <= A[i] <= 5000

题解

原地双指针

用两个指针: lastEven指向数组中最后一个偶数的位置, curr指向当前元素，用来遍历数组。
考虑例子[3,1,2,4]

  1. 初始lastEven指向-1
  2. curr指向0
  3. lastEven curr
  4.       |  |
  5.         [3,  1,  2,  4]
  6. 发现3不是偶数，什么也不做，curr自然往前进一格
  7. lastEven    curr
  8.       |      |
  9.         [3,  1,  2,  4]
  10. 发现1不是偶数，什么也不做，curr自然往前进一格
  11. lastEven        curr
  12.       |          |
  13.         [3,  1,  2,  4]
  14. 发现2是偶数，和lastEven的下一个元素交换位置，然后lastEven向前进一格，得到，
  15.    lastEven         curr
  16.          |           |
  17.         [2,  1,  3,  4]
  18. 最后4也是偶数，再和lastEven的下一个元素交换位置，lastEven向前进一格，
  19.        lastEven         curr
  20.              |           |
  21.         [2,  4,  3,  1]
  1. class Solution {
  2.     public int[] sortArrayByParity(int[] A) {
  3.         for (int lastEven = -1, curr = 0; curr < A.length; curr++) {
  4.             if (A[curr] % 2 == 0) swap(A, ++lastEven, curr);
  5.         }
  6.         return A;
  7.     }
  8.     private void swap(int[] arr, int x, int y) {
  9.         int temp = arr[x];
  10.         arr[x] = arr[y];
  11.         arr[y] = temp;
  12.     }
  13. }

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)