夯实算法-24.按奇偶排序数组 II

题目：LeetCode

给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。 对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

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

示例 1：

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

示例 2：

输入： nums = [2,3]
输出： [2,3]

提示：

• 2 <= nums.length <= 2 * 10410^4104
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

解题思路

题目给定是非负整数数组，这里就没做判空处理。

解法一： 思路分析：设置偶数位和奇数位两个变量，然后从左到右遍历给定数组，

• 若当前位置索引和当前位置的值与2的取余运算相等，说明这些索引位置的元素是满足要求，可以不做调整。
• 继续往后遍历，如果不相等，要判断当前位置应插入奇数位还是偶数位，
• 要判断最后的位置是否是正确的，如果不正确，则调换位置即可

解法二： 思路分析：创建一个临时数组用于存放结果，并同时设置双位置变量，分别表示奇数和偶数，以从左到右顺序遍历给定数组

• 遇到奇数就放入到奇数位置
• 遍历到偶数就放入到偶数位置
• 两个双位置变量相应地加2即可

代码实现

解法一：

public int[] sortArrayByParityII(int[] nums) {
    int i = 0; // 元素下标
    int odd = 0; //指定奇数位置
    int even = 1; //指定偶数位置

    while(i < nums.length){
        if(i % 2 == nums[i] % 2) { // 遍历一遍数组，过滤掉以满足要求的元素，不用对他们做处理
            i++;
            continue;
        }
        if(i % 2 != nums [i] % 2 && i % 2 == 1) { // 当前位置是奇数  需要放在偶数位
            swap(nums, i, odd);
            odd = odd + 2;
        } else if(i % 2 != nums [i] % 2 && i % 2 == 0) { // 当前位置是偶数  需要放在奇数位置
            swap(nums, i, even);
            even = even + 2;
        }
    }
    
    if(k < nums.length && nums[even] % 2 != even %2){
        swap(nums, odd, even);   // 交换元素
    }
    
    return nums;
}

// 交换元素位置
private void swap(int []A, int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

解法二：借助辅助数组

public int[] sortArrayByParityII(int[] nums) {
    int [] ans = new int[nums.length];
    int i = 0; //偶数位
    int j = 1; //奇数位
    int k = 0;
    while (k < nums.length) {
        if (nums[k] % 2 == 0) {  // 位置是偶数  需要放在奇数位置
            ans[i] = nums[k++];
            i = i + 2;
        } else {
            ans[j] = nums[k++]; // 位置是奇数  需要放在偶数位
            j = j + 2;
        }
    }
    return ans;
}

运行结果

解法一：

解法二：

复杂度分析

解法一：

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

解法二：

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)