数组奇数偶数划分

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

如果不保证相对位置不变,那么可以实用快排的思想,但是题目要求相对位置不变,首先可以使用辅助空间的方式。代码如下

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {

        vector<int> odd;
        vector<int> even;
        for(auto c:array)
            {
            if(c%2==1)
                odd.push_back(c);
            else
                even.push_back(c);
        }
        odd.insert(odd.end(),even.begin(),even.end());
        array=odd;

    }
};

如果不借助外在的空间,则首先查找一个奇数,之后将奇数移到第一个位置,之后将第一个奇数之前的位置,向后移动一位,继续查找。

class Solution {
public:
    void reOrderArray(vector<int> &array) 
    {

       int count=1;
       for(int i=0;i!=array.size();++i)
           {
           if(array[i]%2==1)
               {
               int j=i;
               int temp=array[i];
               while(j>=count)
                   {
                   array[j]=array[j-1];
                   --j;
               }
               array[count-1]=temp;
               ++count;
           }
       }

    }
};
    原文作者:njudongchen
    原文地址: https://blog.csdn.net/njudongchen/article/details/61193095
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞