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

偏执的太偏执、 2021-12-17 15:59 169阅读 0赞

题目描述：

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

解题思路：

思路一：借助辅助空间，遍历一遍数组，将奇数和偶数分别存入两个队列，再分别情况奇数队列和偶数队列，就对应的数转移到原数组上。

思路二：实际面试中，一般是需要考察这道题利用插入排序的思想。既然要将奇数放在前面偶数放在后面，那么就扫描数组，找到第一个偶数位置为i，再找该偶数后面的第一个奇数为j，将i到j-1的所有数往后移动一位，再将这个j上的奇数放到i上。接下来，从当前这个奇数向后扫描，同样找到第一个偶数，以及偶数后的第一个奇数，按照之前的方式移动偶数，并填补奇数位置。这样就不需要用到额外的数组空间来存数。注意每次移动完偶数后，需要将原始指向第一个偶数的指针后移，因为此时这个i的位置指向的是奇数。

代码：

思路一：

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            queue<int> odd;
            queue<int> even;
            for(int i=0; i<array.size(); i++)
            {
                if(array[i]%2==0)
                    even.push(array[i]);
                else
                    odd.push(array[i]);
            }
            int i;
            int odd_size = odd.size();
            for(i=0; i<odd_size; i++)
            {
                array[i] = odd.front();
                odd.pop();
            }
            int even_size = even.size();
            for(i; i<(odd_size+even_size); i++)
            {
                array[i] = even.front();
                even.pop();
            }
        }
    };

思路二：

class Solution {
    public:
        void reOrderArray(vector<int> &array) {
            if(array.empty() || array.size()==1)
                return;
            int temp;
            for(int i=0;i<array.size();i++)
            {
                if(array[i]%2==0)//找到第一个偶数的位置
                {
                     for(int j=i+1;j<array.size();j++)
                     {
                         if(array[j]%2==1)//从第一个偶数往后找到第一个奇数的位置
                         {
                             temp=array[j];//先保存下奇数位置
                             while(j>i)//把偶数后移一个位置
                             {
                                 array[j]=array[j-1];
                                 j--;
                             }
                             array[j]=temp;//空出来的位置填上奇数
                             i++; //表示所有偶数都已经后移了一位，对应指向第一个偶数的指针也后移
                         }
                     }
                }
            }
        }
    };

转载于:https://www.cnblogs.com/LJ-LJ/p/10587847.html