922. Sort Array By Parity II

Problem

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?

Approach

• Đề bài: mảng có độ dài là số chẵn, chia thành 2 tập: số chẵn và số lẻ. Sort mảng sao cho giá trị tại index chẵn là số chẵn, giá trị tại index lẻ là số lẻ
• Dùng 2 pointer: p_even và p_odd là lần lượt là pointer tại các index chẵn và lẻ
• Do chỉ có 2 tập chẵn lẻ, do đó nếu ta sắp xếp sao cho giá trị tại các index chẵn là số chẵn, thì tập lẻ tự khắc sẽ đúng
• Đơn giản, ta chỉ cần duyệt qua lần lượt các vị trí index chẵn p_even:
  • Nếu giá trị tại index chẵn là chẵn (hợp lệ): tiếp tục duyệt phần tử chẵn tiếp theo p_even += 2
  • Nếu giá trị tại index chẵn là lẻ (không hợp lệ): tiến hành tìm kiếm 1 phần tử khác ở vị trí lẻ p_even không hợp lệ (index lẻ nhưng mang giá trị chẵn) để swap 2 giá trị này cho nhau

Implementation

class Solution {
    private int[] nums;

    public int[] sortArrayByParityII(int[] nums) {
        this.nums = nums;
        int p_even = 0;
        int p_odd = 1;

        while (p_even < nums.length) {
            if (isEven(nums[p_even])) {
                p_even += 2;
            } else {
                // Tim phan tu o vi tri odd 1, 3, 5,... dau tien co gia tri chan (even)
                while (p_odd < nums.length && isOdd(nums[p_odd])) {
                    p_odd += 2;
                }
                if (p_odd < nums.length) {
                    swap(p_even, p_odd);
                }               
                p_even += 2;
            }
        }

        return nums;
    }

    private void swap(int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    private static boolean isEven(int x) {
        return x % 2 == 0;
    }

    private static boolean isOdd(int x) {
        return x % 2 != 0;
    }
}