【力扣】922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii

//时间复杂度O(n) 空间复杂度O(n)

    public int[] sortArrayByParityII(int[] A) {

        //错误的奇数索引

        List<Integer> errorOddNumber = new ArrayList<>();

        //错误的偶数索引

        List<Integer> errorEvenNumber = new ArrayList<>();

        for(int i = 0; i < A.length; i++){

            if(i%2 ==0){ //是偶数索引吗?

                if(A[i] % 2 != 0){ //值是否为偶数

                    errorEvenNumber.add(i);

                }

            } else {

                if(A[i] % 2 != 1){ //值是否为奇数

                    errorOddNumber.add(i);

                }

            }

        }

        int i = 0;

        int temp  = 0;

        //对奇偶数交换

        while(i<errorEvenNumber.size() && i < errorOddNumber.size()){

            int a = errorEvenNumber.get(i);

            int b = errorOddNumber.get(i);

            temp = A[a];

            A[a] = A[b];

            A[b] = temp;

            i++;

        }

        return A;

    }

时间复杂度：O（n）

空间复杂度：O（1）

//有没有办法做到不使用额外的空间？

    //使用双指针

    public int[] sortArrayByParityII(int[] A) {

        //奇数索引的指针

        int oddIndex = 1;

        //偶数索引的指针

        int evenIndex = 0;

        //每次挪动两步，为了保证都是走的同种类型的索引

        for(;evenIndex < A.length ; evenIndex+=2){

            //如果偶数索引对应的并非是偶数的值

            if(A[evenIndex]%2 != 0){

                for(;oddIndex < A.length;oddIndex+=2){

                    //那么找到同种类型的不满足的奇数索引，将两个置换

                    if(A[oddIndex]%2 != 1){

                        swap(A,evenIndex,oddIndex);

                        break;

                    }

                }

            }

        }

        return A;

    }

    private void swap(int[] A, int a, int b){

        int temp = A[a];

        A[a] = A[b];

        A[b] = temp;

    }

【力扣】922. 按奇偶排序数组 II的相关教程结束。