Question

905. 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

Solutions

Solution 1: Two Pointers

We use two pointers $i$ and $j$ to point to the beginning and end of the array respectively. When $i < j$, we perform the following operations.

• If $nums[i]$ is even, then increment $i$ by $1$.
• If $nums[j]$ is odd, then decrement $j$ by $1$.
• If $nums[i]$ is odd and $nums[j]$ is even, then swap $nums[i]$ and $nums[j]$. Then increment $i$ by $1$, and decrement $j$ by $1$.

Finally, return the array $nums$.

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

class Solution:
  def sortArrayByParity(self, nums: List[int]) -> List[int]:
    i, j = 0, len(nums) - 1
    while i < j:
      if nums[i] % 2 == 0:
        i += 1
      elif nums[j] % 2 == 1:
        j -= 1
      else:
        nums[i], nums[j] = nums[j], nums[i]
        i, j = i + 1, j - 1
    return nums

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

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

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

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

impl Solution {
  pub fn sort_array_by_parity(mut nums: Vec<i32>) -> Vec<i32> {
    let (mut i, mut j) = (0, nums.len() - 1);
    while i < j {
      if nums[i] % 2 == 0 {
        i += 1;
      } else if nums[j] % 2 == 1 {
        j -= 1;
      } else {
        nums.swap(i, j);
        i += 1;
        j -= 1;
      }
    }
    nums
  }
}

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