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

解1：调整数组顺序使奇数位于偶数前面 I

🚩传送门：牛客题目

题目

输入一个长度为 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变，但是时间复杂度和空间复杂度必须如下要求。

要求：时间复杂度 ，空间复杂度

解题思路：模拟

将原数组的奇数偶数按顺序拷贝下来

复杂度分析

时间复杂度：，其中 为数组的长度。每个元素只会被遍历 2 次。

空间复杂度：，我们只需新建一个长度为的数组。

我的代码

public class Solution {
    public int[] reOrderArray(int[] array) {
        int n = array.length;
        int[] arr = new int[n];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if ((array[i] & 1) == 1)
                arr[j++] = array[i];
        }
        for (int i = 0; i < n; i++) {
            if ((array[i] & 1) == 0)
                arr[j++] = array[i];
        }
        return arr;
    }
}

解2：调整数组顺序使奇数位于偶数前面 II

🚩传送门：牛客题目
力扣题目

题目

输入一个长度为 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

要求：时间复杂度 ，空间复杂度

示例：

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

解题思路：双指针 I

使用 和 双指针，其中：

1. 区间都是奇数，为已处理部分
2. 区间都是偶数部分
3. 区间都是未处理部分

指针 从前向后遍历，遇到偶数不管，遇到奇数，如果和 指针不等则互换

复杂度分析

时间复杂度：，其中 为数组的长度。每个元素只会被遍历一次。

空间复杂度：，我们只需常数空间。

我的代码

public class Solution {
    public void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public int[] reOrderArrayTwo(int[] array) {
        int i = 0;
        for (int j = 0; j < array.length; j++) {
            // 判断是否是奇数,奇数互换、偶数不管
            if ((array[j] & 1) == 1) {
                if (i == j) {
                    i++;    // i,j相同没必要互换,i下移就好
                } else {
                    swap(array, i++, j);
                }
            }
        }
        return array;
    }
}

解题思路：双指针 II

考虑定义双指针 , 分列数组左右两端，循环执行：

• 指针 从左向右寻找偶数；
• 指针从右向左寻找奇数；
• 将 偶数 和 奇数 交换。

可始终保证： 指针 ,左边都是奇数，指针右边都是偶数 。

复杂度分析

时间复杂度：，其中 为数组的长度。每个元素只会被遍历一次。

空间复杂度：，我们只需常数空间。

我的代码

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int tmp;
        while(i < j) {
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}