LeetCode 922: Sort Array By Parity II (Index-Parity Placement)

2026-04-10 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 922ArrayTwo Pointers

Today we solve LeetCode 922 - Sort Array By Parity II.

Source: https://leetcode.com/problems/sort-array-by-parity-ii/

LeetCode 922 diagram showing even numbers placed at even indices and odd numbers at odd indices

English

Problem Summary

Given an array where exactly half the integers are even and half are odd, rearrange it so that values at even indices are even and values at odd indices are odd.

Key Insight

Track two index pointers: i visits even indices (0,2,4...), and j visits odd indices (1,3,5...). If an even index has an odd number, find an odd index that incorrectly has an even number, then swap.

Algorithm

- Initialize i = 0 for even positions and j = 1 for odd positions.
- Move i by 2 while nums[i] is even.
- When nums[i] is odd, move j by 2 until nums[j] is even.
- Swap nums[i] and nums[j], continue until i reaches end.

Complexity Analysis

Time: O(n).
Space: O(1) extra.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func sortArrayByParityII(nums []int) []int {
    j := 1
    for i := 0; 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
}

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

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

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

中文

题目概述

给定一个数组，其中一半元素是偶数、一半是奇数。请重排数组，使偶数下标位置放偶数，奇数下标位置放奇数。

核心思路

使用两个按步长 2 前进的指针：i 只检查偶数下标，j 只检查奇数下标。当 i 位置错放了奇数时，去找一个错放偶数的奇数下标 j，交换即可一次修复两个位置。

算法步骤

- 设 i=0（偶数位），j=1（奇数位）。
- 遍历偶数位：如果 nums[i] 是偶数，继续；否则说明该位错误。
- 移动 j，直到找到一个放了偶数的奇数下标。
- 交换 nums[i] 与 nums[j]，继续处理下一个偶数位。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func sortArrayByParityII(nums []int) []int {
    j := 1
    for i := 0; 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
}

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

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

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