剑指offer—调整数组使得奇数在偶数前面 解答

剑指offer—调整数组使得奇数在偶数前面

题目描述

给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。

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

示例:

输入:[3,1,2,4]
输出:[2,4,3,1]
输出 [4,2,3,1],[2,4,1,3] 和 [4,2,1,3] 也会被接受。

思路

  • 遍历数组,之前是偶数就移动到数组末尾(把后面的数都往前移动一位):时间复杂度$N^2$

  • 快排(前后指针依次移动,前面碰到偶数停下,后面碰到奇数停下,都停下后进行交换):时间复杂度O(N)

优化:使用位运算判断奇偶数

代码

public class Solution {
    public void reOrderArray(int [] array) {
        int low = 0;int high = array.length-1;
        while(low<high){
            while((low<high)&&(array[low]&1)==1){//偶数停下
                low++;
            }
            while((low<high)&&(array[high]&1)!=1){//奇数停下
                high--;
            }
            if(low<high){//交换
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
        }
    }
}

扩展

  • 给定一个非负整数数组 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] 也会被接受。

思路

  • 方法1:使用辅助空间,新开一个数组,遍历数组,偶数存储到0,2,4,6等偶数标位置,奇数存储到1,3,5,7等奇数处位置:时间复杂度N,空间复杂度N

  • 方法2:使用双指针,分别指向数组奇数和偶数,奇数指针循环如果数组值为偶则停下,偶数指针如果遍历带数组值为奇数则停下,此时如果都在数组范围内则进行交换:时间复杂度N,空间复杂度O(1)

代码

class Solution {
    public int[] sortArrayByParityII(int[] a) {
        int i = 0,j = 1;
        while(i<=a.length-1&&j<=a.length-1){//数组内循环
            while(i<=a.length-1&&(a[i]&1)==0){//偶数指针循环找奇数
                i+=2;
            }
            while(j<=a.length-1&&(a[j]&1)==1){//奇数指针循环找偶数
                j+=2;
            }
            if((i<=a.length-1)&&(j<=a.length-1)){//如果在数组内,交换
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        return a;
    }
}