按奇偶排序数组II

LeetCode每日一题，922. Sort Array By Parity II

先看题目描述

大意就是给定一个数组，这个数组中一半是奇数，一半是偶数，让我们给这个数组排序，保证当 i 是奇数时，A[i] 为奇数；当 i 是偶数时，A[i] 为偶数

算法和思路

使用两个栈

大致思路就是一次遍历，用一个长度为2的双向队列数组存储位置不对的数，当碰到一个奇数处于偶数位置时，若此时 indexs[0] 为空，则将其下标存储入 indexs[1] 中，若 indexs[0] 不为空，则弹出 indexs[1] 中的最后一个元素，然后将这个下标对应的数字与当前数字交换；若碰到一个偶数处于奇数位置，也是同样的操作，若 indexs[1] 不为空，则弹出下标，并将其对应数字与当前数字交换，否则就将当前下标添加入 indexs[0] 中，遍历完后返回交换后的数组即可

一次遍历+双指针(不修改原数组)

先定义一个长度与原数组相同的 ans 数组，用于储存最后的结果。然后定义两个指针 m 和 n，并初始化 m = 0， n = 1，然后遍历原数组，当遇到偶数时，则将其值赋给 ans[m]，并将 m 往后移动两位；遇到奇数时，则将其值赋给 ans[n]，并将 n 向后移动两位。遍历完后返回 ans 数组即可

一次遍历+双指针(修改原数组)

若原数组可修改，那我们没必要定义一个新数组，在原数组的基础上交换元素即可。同样是定义两个指针 i 和 j，初始化 i = 0，j = 1，然后每次将 i 指针往后移动两位，当遇到奇数时，则指针 i 停止移动，然后开始移动 j 指针，也是每次往后移动两位直至遇到偶数，此时将 i 指针指向的数字和 j 指针指向的数字交换即可。重复上述过程，直至遍历完整个数组，然后返回交换后的数组即可

算法源码

使用两个栈

import java.util.*;

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        Deque<Integer>[] indexs = new Deque[2];
        for (int i = 0; i < 2; i++) {
            indexs[i] = new ArrayDeque<>();
        }
        int len = A.length;
        for (int i = 0; i < len; i++) {
            int remainder = A[i] % 2;
            if (remainder != i % 2) {
                if (!indexs[1 - remainder].isEmpty()) {
                    int j = indexs[1 - remainder].removeLast();
                    swap(A, i, j);
                } else {
                    indexs[remainder].add(i);
                }
            }
        }
        return A;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

这个的效率会比较低，因为对双向队列的这些操作还是挺耗时的

一次遍历+双指针(不修改原数组)

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int len = A.length;
        int[] ans = new int[len];
        int m = 0;
        int n = 1;
        for (int num : A) {
            if (num % 2 == 0) {
                ans[m] = num;
                m += 2;
            } else {
                ans[n] = num;
                n += 2;
            }
        }
        return ans;
    }
}

一次遍历+双指针(修改原数组)

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

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}