Question

922. Sort Array By Parity II

中文文档

Description

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return _any answer array that satisfies this condition_.

 

Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]
Output: [2,3]

 

Constraints:

• 2 <= nums.length <= 2 * 104
• nums.length is even.
• Half of the integers in nums are even.
• 0 <= nums[i] <= 1000

 

Follow Up: Could you solve it in-place?

Solutions

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to even and odd indices respectively.

When $i$ points to an even index, if $nums[i]$ is odd, then we need to find an odd index $j$ such that $nums[j]$ is even, and then swap $nums[i]$ and $nums[j]$. Continue to iterate until $i$ points to the end of the array.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

class Solution:
  def sortArrayByParityII(self, nums: List[int]) -> List[int]:
    n, j = len(nums), 1
    for i in range(0, n, 2):
      if nums[i] % 2:
        while nums[j] % 2:
          j += 2
        nums[i], nums[j] = nums[j], nums[i]
    return nums

class Solution {
  public int[] sortArrayByParityII(int[] nums) {
    for (int i = 0, j = 1; i < nums.length; i += 2) {
      if (nums[i] % 2 == 1) {
        while (nums[j] % 2 == 1) {
          j += 2;
        }
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    return nums;
  }
}

class Solution {
public:
  vector<int> sortArrayByParityII(vector<int>& nums) {
    for (int i = 0, j = 1; i < nums.size(); i += 2) {
      if (nums[i] % 2) {
        while (nums[j] % 2) {
          j += 2;
        }
        swap(nums[i], nums[j]);
      }
    }
    return nums;
  }
};

func sortArrayByParityII(nums []int) []int {
  for i, j := 0, 1; i < len(nums); i += 2 {
    if nums[i]%2 == 1 {
      for nums[j]%2 == 1 {
        j += 2
      }
      nums[i], nums[j] = nums[j], nums[i]
    }
  }
  return nums
}

function sortArrayByParityII(nums: number[]): number[] {
  for (let i = 0, j = 1; i < nums.length; i += 2) {
    if (nums[i] % 2) {
      while (nums[j] % 2) {
        j += 2;
      }
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  return nums;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParityII = function (nums) {
  for (let i = 0, j = 1; i < nums.length; i += 2) {
    if (nums[i] % 2) {
      while (nums[j] % 2) {
        j += 2;
      }
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  return nums;
};