每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面

终有救赎

发布于 2023-10-16 10:18:58

1520

发布于 2023-10-16 10:18:58

文章被收录于专栏：多线程

今天题目有两道，分为一和二题目链接：调整数组顺序使奇数位于偶数前面(一) 题目链接：调整数组顺序使奇数位于偶数前面(二)

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

难度：中等

描述

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围

数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000

要求：时间复杂度 O(n)，空间复杂度 O(n)

进阶：时间复杂度 O(n2)，空间复杂度 O(1)

举例

解题思路

首先，如果不考虑奇数和奇数，偶数和偶数的相对位置，那么我们有一种双指针解法来求解，类似于快排，维护两个指针，第一个指针指向数组的第一个数字，第二个指针指向数组的最后一个数字。第一个指针向后移，第二个指针向前移，如果第一个指针指向偶数，第二个指针指向的是奇数，则交换着两个数字，接着继续移动直到两指针相遇。

上面的方法看似不错，但是对本题不适用，因为本题有相对位置不变的要求，直接交换会导致相对位置改变。因此，我们采用下面的思路来解决本题。

本题解法：对数组进行遍历，设置两个指针even和odd，even指向当前第一个偶数，odd从这个偶数之后开始查找，找到第一个奇数，此时为了相对位置不变，不能直接交换even和odd，而是将从even到odd-1的元素都依次向后移一个位置，将odd指向的那个奇数放到even的位置。然后再找下一个偶数，重复这一过程，最终就可以将奇数都放到偶数的前面，并且保证了相对位置的不变。

编程实现（java）

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int i = 0,j = 0;
        int n = array.length;
        while(i<n && j<n){
            //找到第一个偶数
            while(i<n && array[i]%2!=0){
                i++;
            }

            //找到第一个偶数后的第一个奇数
            j= i+1;
            while(j<n && array[j]%2==0){
                j++;
            }

            //注意判断，防止溢出
            if(j>=n) break;

            //把偶数与奇数之间的所有偶数往后移动，奇数与该偶数位置的元素对调
            //先把偶数后第一个奇数保存下来，因为接下来的移动过程中会替换掉该奇数
            int t = array[j];
            for(int k = j-1;k>= i;k--){
                array[k+1] = array[k];
            }
            //把奇数填到第一个偶数往后移动，所腾出来的位置
            array[i] = t;
            i++;
        }
        return array;
    }
}

结果

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

难度：简单

描述

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

数据范围

数据范围：0≤n≤50000，数组中每个数的值 0≤val≤10000

要求：时间复杂度 O(n)，空间复杂度 O(1)

举例

解题思路

这道题不需要要求相对位置不变，因此我们可以采用位置交换的方法，只要奇数全部换到前面就可以了。

利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况。

编程实现（java）

import java.util.*;
public class Solution {
    public int[] reOrderArrayTwo (int[] array) {
        //双指针
        int i = 0;
        int j = array.length - 1; 
        //向中间聚合
        while(i < j){ 
            //左右都是奇数，左移右不动
            if(array[i] % 2 == 1 && array[j] % 2 == 1) 
                i++;
            //左奇数右偶数，左右都向中间缩
            else if(array[i] % 2 == 1 && array[j] % 2 == 0){
                i++;
                j--;
            }
            //左偶右奇数
            else if(array[i] % 2 == 0 && array[j] % 2 == 1){
                //交换
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
            //左右都是偶数，只移动右指针
            else 
                j--;
        }
        return array;
    }
}