Leetcode922 按奇偶排序数组 II

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

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

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

思路：双指针

如果原数组可以修改，则可以使用就地算法求解。

为数组的偶数下标部分和奇数下标部分分别维护指针 i, j。随后，在每一步中，如果 nums[i] 为奇数，则不断地向前移动 j每次移动两个单位，直到遇见下一个偶数。此时，可以直接将 nums[i] 与 nums[j] 交换。我们不断进行这样的过程，最终能够将所有的整数放在正确的位置上。

实现代码：

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

    int j = 1;
    for(int i = 0; i < nums.length; i+=2){
        if(nums[i] % 2 == 1){

            while(nums[j] % 2 == 1){
                j += 2;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    return nums;
}