题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

样例

输入：[1,2,3,4,5]

输出: [1,3,5,2,4]

算法

(双指针扫描) $O(n)$

用两个指针分别从首尾开始，往中间扫描。扫描时保证第一个指针前面的数都是奇数，第二个指针后面的数都是偶数。

每次迭代时需要进行的操作：

1. 第一个指针一直往后走，直到遇到第一个偶数为止；
2. 第二个指针一直往前走，直到遇到第一个奇数为止；
3. 交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止；

时间复杂度

当两个指针相遇时，走过的总路程长度是 $n$，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int i=0,j=array.size()-1;
        while(i<j){
            while(i<j&&array[i]%2==1)i++;
            while(i<j&&array[j]%2==0)j--;
            swap(array[i],array[j]);
        }
    }
};

C 代码

void reOrderArray(int *array, int length) {
        int i=0,j=length-1;
        while(i<j){
            while(i<j&&array[i]%2==1)i++;
            while(i<j&&array[j]%2==0)j--;
            int t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
}

Java 代码

class Solution {
    public void reOrderArray(int [] array) {
        int i=0;
        int j=array.length-1;
        while(i<j){
            while(i<j&&array[i]%2==1)i++;
            while(i<j&&array[j]%2==0)j--;
            int t=array[i];
            array[i]=array[j];
            array[j]=t;
        }
    }
}

Python 代码

class Solution(object):
    def reOrderArray(self, array):
        """
        :type array: List[int]
        :rtype: void
        """
        i=0
        j=len(array)-1
        while i<j:
            while i<j and array[i]%2==1:
                i+=1
            while i<j and array[j]%2==0:
                j-=1
            t=array[i]
            array[i]=array[j]
            array[j]=t

Javascript 代码

/**
 * @param {number[]} array
 * @return {void}
 */
var reOrderArray = function(array) {
    var i=0,j=array.length-1;
    while(i<j){
        while(i<j&&array[i]%2==1)i++;
        while(i<j&&array[j]%2==0)j--;
        var t=array[i];
        array[i]=array[j];
        array[j]=t;
    }
};

Python3 代码

class Solution(object):
    def reOrderArray(self, array):
        """
        :type array: List[int]
        :rtype: void
        """
        i=0
        j=len(array)-1
        while i<j:
            while i<j and array[i]%2==1:
                i+=1
            while i<j and array[j]%2==0:
                j-=1
            t=array[i]
            array[i]=array[j]
            array[j]=t

Go 代码

func reOrderArray(array []int){
    i,j:=0,len(array)-1
    for i<j{
        for i<j&&array[i]%2==1{
            i++
        }
        for i<j&&array[j]%2==0{
            j--
        }
        array[i],array[j]=array[j],array[i]
    }
}

记得点赞后在走哦…
谢谢大家的赞！
看我写了155行的面子上点个赞哦。