按奇偶排序数组

按奇偶排序数组

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

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

示例：

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

提示：

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

双指针

public int[] sortArrayByParity(int[] A) {
    int low = 0, high = A.length - 1;
    while (low < high) {
        if (A[low] % 2 == 0) {
            low++;
        } else if (A[high] % 2 != 0) {
            high--;
        } else {
            int temp = A[low];
            A[low++] = A[high];
            A[high--] = temp;
        }
    }
    return A;
}

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一

和上题一样
方法一：双指针

public int[] exchange(int[] nums) {
    int i=0;
    int j=nums.length-1;
    while(i<j){
        if((nums[i]&1)!=0){
            i++;
        } else if((nums[j]&1)==0){
            j--;
        } else {
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;               
        }
    }
    return nums;
}

类似快排的方式

public int[] exchange(int[] nums) {
    int i = 0;
    int j = nums.length - 1;
    while (i < j) {
        while (i < j && (nums[i] & 1) != 0) {
            i++;
        }
        while (i < j && (nums[j] & 1) == 0) {
            j--;
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    }
    return nums;
}

方法二：快慢指针

• fast的作用是向前搜索奇数位置,slow的作用是指向下一个奇数应当存放的位置
• fast 向前移动，当它搜索到奇数时，将它和 nums[slow]交换，此时slow向前移动一个位置
• 重复上述操作，直到 fastfast 指向数组末尾

public int[] exchange(int[] nums) {
    int slow = 0;
    int fast = 0;
    while (fast < nums.length) {
        if ((nums[fast] & 1) != 0) {
            int temp = nums[fast];
            nums[fast] = nums[slow];
            nums[slow] = temp;
            slow++;
        }
        fast++;
    }
    return nums;
}

按奇偶排序数组 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] 也会被接受。

提示：

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

双指针
维护指向偶数位置和奇数位置的指针，如果偶数位不是偶数，奇数指针向前查找到偶数进行交换

public int[] sortArrayByParityII(int[] A) {
    int even = 0, odd = 1;
    while (even < A.length) {
        if (A[even] % 2 != 0) {
            while (A[odd] % 2 != 0) {
                odd += 2;
            }
            int temp = A[even];
            A[even] = A[odd];
            A[odd] = temp;
        } else {
            even += 2;
        }
    }
    return A;
}