剑指offer | 调整数组顺序使奇数位于偶数前面 | 08

目录

• 思路分析
• 双指针算法
• 辅助数组

思路分析

如果这个题目不要求相对位置不改变的话,那么就是快速排序的一个双指针算法.

如果要保证相对位置不改变的话,那么就要开一个辅助数组.

双指针算法

cpp

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        if(nums.empty())return nums;
        int i=0,j=nums.size()-1;
        while(i<j){
            while(i<j && nums[i]%2!=0)i++;
            while(i<j && nums[j]%2==0)j--;
            if(i<j)swap(nums[i],nums[j]);
        }
        return nums;
    }
};

python

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        if not nums:return nums
        i,j=0,len(nums)-1
        while i<j:
            while i<j and nums[i]%2!=0:i+=1
            while i<j and nums[j]%2==0:j-=1
            if i<j:nums[i],nums[j]=nums[j],nums[i]
        return nums

辅助数组

cpp

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> help;
        for(auto x:array){
            if(x%2!=0)help.push_back(x);
        }
        for(auto x:array){
            if(x%2==0)help.push_back(x);
        }
        copy(help.begin(),help.end(),array.begin());
    }
};

python

#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def reOrderArray(self , array ):
        helper = []
        for x in array:
            if x%2!=0: helper.append(x)
        for x in array:
            if x%2==0: helper.append(x)
        return helper