You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

922. 按奇偶排序数组 II - Sort Array By Parity II

. 1 min read

【双指针】

给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。

对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

Example:

示例:

输入:[4,2,5,7]
输出:[4,5,2,7]
解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。

提示:

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 0 <= A[i] <= 1000

Solutions

Solution 【双指针】 ( 7ms) O(N)

class Solution {
  public int[] sortArrayByParityII(int[] A) {
    int idx_even = 0;
    int idx_odd = 1;
    int length = A.length;
    while (idx_even < length && idx_odd < length) {
      while (idx_even < length && A[idx_even] % 2 == 0) {
        idx_even += 2;
      }
      while (idx_odd < length && A[idx_odd] % 2 == 1) {
        idx_odd += 2;
      }
      if (!(idx_even < length && idx_odd < length)) {
        break;
      }
      int tmp = A[idx_even];
      A[idx_even] = A[idx_odd];
      A[idx_odd] = tmp;
      idx_even += 2;
      idx_odd += 2;
    }
    return A;
  }
}

Solution  ( 5ms)

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int j = 1;
        for (int i = 0; i < A.length; i += 2) {
            if ((A[i] & 1) != 0) {
                while ((A[j] & 1) != 0) {
                    j += 2;
                }
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            } 
        }
        return A;
    }
}

思路相同,但速度更快,可借助1理解2