剑指offer 面试题21 调整数组顺序使奇数位于偶数前面

wenkun97

于 2019-11-08 00:03:10 发布

阅读量124

点赞数

分类专栏：剑指offer 文章标签：剑指offer

本文链接：https://blog.csdn.net/hello_my_coder/article/details/102965309

版权

剑指offer 专栏收录该内容

53 篇文章

订阅专栏

本文介绍了一种在数组中调整数字顺序的算法，确保所有奇数位于前半部分，所有偶数位于后半部分，同时保持同类数字间的相对位置不变。通过遍历数组并调整奇数位置，实现了这一目标。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

由于需要保持奇数之间和偶数之间的相对位置不变，每次都要把奇数向前移若干位，复杂度为o(n²)，不知道有没有更优的解法。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.size()<=1) {
            return ;
        }
        int index_even=-1;
        for(int i=0;i<array.size();i++) {
            if(array[i]&0x01) {
                if(index_even!=-1) {
                    int pos=index_even;
                    int index_odd=i;
                    while(array[pos]%2==0&&pos>=0) {
                        int temp=array[index_odd];
                        array[index_odd]=array[pos];
                        array[pos]=temp;
                        index_odd=pos;
                        pos--;
                    }
                    index_even=i;
                }
            } else {
                index_even=i;
            }
        }
    }
};