Skip to main content

922. 按奇偶排序数组II

力扣题目链接leetcode.cn力扣题目链接/problems/sort-array-by-parity-ii/

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

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

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

示例：

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

思路​

这道题目直接的想法可能是两层for循环再加上used数组表示使用过的元素。这样的的时间复杂度是O(n^2)。

方法一​

其实这道题可以用很朴实的方法，时间复杂度就就是O(n)了，C++代码如下：

C++
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> even(nums.size() / 2); // 初始化就确定数组大小，节省开销
        vector<int> odd(nums.size() / 2);
        vector<int> result(nums.size());
        int evenIndex = 0;
        int oddIndex = 0;
        int resultIndex = 0;
        // 把nums数组放进偶数数组，和奇数数组
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) even[evenIndex++] = nums[i];
            else odd[oddIndex++] = nums[i];
        }
        // 把偶数数组，奇数数组分别放进result数组中
        for (int i = 0; i < evenIndex; i++) {
            result[resultIndex++] = even[i];
            result[resultIndex++] = odd[i];
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

方法二​

以上代码我是建了两个辅助数组，而且nums数组还相当于遍历了两次，用辅助数组的好处就是思路清晰，优化一下就是不用这两个辅助数组，代码如下：

C++
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> result(nums.size());
        int evenIndex = 0;  // 偶数下标
        int oddIndex = 1;   // 奇数下标
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) {
                result[evenIndex] = nums[i];
                evenIndex += 2;
            }
            else {
                result[oddIndex] = nums[i];
                oddIndex += 2;
            }
        }
        return result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

方法三​

当然还可以在原数组上修改，连result数组都不用了。

C++
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int oddIndex = 1;
        for (int i = 0; i < nums.size(); i += 2) {
            if (nums[i] % 2 == 1) { // 在偶数位遇到了奇数
                while(nums[oddIndex] % 2 != 0) oddIndex += 2; // 在奇数位找一个偶数
                swap(nums[i], nums[oddIndex]); // 替换
            }
        }
        return nums;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

这里时间复杂度并不是O(n^2)，因为偶数位和奇数位都只操作一次，不是n/2 * n/2的关系，而是n/2 + n/2的关系！

其他语言版本​

Java
// 方法一
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        // 分别存放 nums 中的奇数、偶数
        int len = nums.length;
        int evenIndex = 0;
        int oddIndex = 0;
        int[] even = new int[len / 2];
        int[] odd = new int[len / 2];
        for (int i = 0; i < len; i++) {
            if (nums[i] % 2 == 0) {
                even[evenIndex++] = nums[i];
            } else {
                odd[oddIndex++] = nums[i];
            }
        }
        // 把奇偶数组重新存回 nums
        int index = 0;
        for (int i = 0; i < even.length; i++) {
            nums[index++] = even[i];
            nums[index++] = odd[i];
        }
        return nums;
    }
}
Java
//方法一：采用额外的数组空间
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        //定义结果数组 result
        int[] result = new int[nums.length];
        int even = 0, odd = 1;
        for(int i = 0; i < nums.length; i++){
            //如果为偶数
            if(nums[i] % 2 == 0){
                result[even] = nums[i];
                even += 2;
            }else{
                result[odd] = nums[i];
                odd += 2;
            }
        }
        return result;
    }
}
Java
//方法二：不采用额外的数组空间
class Solution922 {
    public int[] sortArrayByParityII(int[] nums) {
        //定义双指针
        int oddPoint = 1, evenPoint = 0;
        //开始移动并交换，最后一层必然为相互交换后再移动或者相同直接移动
        while(oddPoint < nums.length && evenPoint < nums.length){
            //进行判断
            if(nums[oddPoint] % 2 == 0 && nums[evenPoint] % 2 == 1){    //如果均不满足
                int temp = 0;
                temp = nums[oddPoint];
                nums[oddPoint] = nums[evenPoint];
                nums[evenPoint] = temp;
                oddPoint += 2;
                evenPoint += 2;
            }else if(nums[oddPoint] % 2 == 0 && nums[evenPoint] % 2 == 0){  //偶数满足
                evenPoint += 2;
            }else if(nums[oddPoint] % 2 == 1 && nums[evenPoint] % 2 == 1){  //奇数满足
                oddPoint += 2;
            }else{
                oddPoint += 2;
                evenPoint += 2;
            }
        }
        return nums;
    }
}