题解 | #调整数组顺序使奇数位于偶数前面#

一.题目描述
NC77
题目链接:
https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=188&&tqId=38597&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
二.算法(暴力)
直接利用两个vector分别存储奇数和偶数，然后把偶数数组全部插入放入奇数数组，下面是完整代码:

class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        vector<int>a;
        vector<int>b;
        for(int i=0;i<array.size();i++){
            if(array[i]%2){//偶数
                a.push_back(array[i]);
            } else {//奇数
                b.push_back(array[i]);
            }
        }
        //将偶数插入奇数后部
        for(int i=0;i<b.size();i++){
            a.push_back(b[i]);
        }
        return a;
    }
};

时间复杂度： $o(n)$ 对每一个元素都要判断分组，后插入
空间复杂度: $o(n)$ 需要而且额外空间来存储
优缺点: 实现起来简单，但是空间利用率不高
三.算法(双指针)

定义头指针left和尾指针right。
left一直往右移，直到它指向的值为偶数。
right一直往左移，直到它指向的值为奇数
交换nums[left]和nums[right]。
重复上述操作，直到left==right。

如果按照上述双指针进行简单的交换是可以实现奇数位于偶数前面但是无法保证相对顺序(也就是后面的偶数会倒过来放置在前面)，所有我们应该在交换时注意：

首先我们应该只能从一边开始遍历，只有这样才可以保证相对顺序

然后到了关键的步骤，找到第一个奇数 $i$ ，和第一个偶数 $j$ 后，继续寻找第二个奇数 $i'$ ,然后把 $i'$ 到 $j$ 的元素向后移，把i'放到j的位置上。模仿直接插入排序。

下面给出完整的代码:

class Solution {
public:
  vector<int> reOrderArray(vector<int>& array) {
      int oddIndex=0,evenIndex=0;
      int n=array.size();
      if(n==0) return {};
      //找到第一个为偶数的
      while(array[evenIndex]%2){
          evenIndex++;
      }
      //找到在第一个偶数后的第一个奇数
      while(array[oddIndex]%2==0||oddIndex<evenIndex){
          oddIndex++;
      }
      //将奇数交换到第一个偶数的位置，在该奇数之前的所有偶数向后顺延一个位置
      while(oddIndex<n&&evenIndex<n){
          int tmp=array[oddIndex];
          for(int i=oddIndex;i>evenIndex;i--){
              array[i]=array[i-1];
          }
          array[evenIndex]=tmp;
          //对两个指针位置进行更新
          evenIndex++;
          while(oddIndex<n&&array[oddIndex]%2==0)
              oddIndex++;
      }
      return array;
  }
};

时间复杂度： $o(2*n)$ 两个指针都要遍历一遍
空间复杂度： $o(1)$ 不需要额外开辟空间
优缺点:时间复杂度不高，而且空间复杂度也不高，但是实现起来麻烦