《剑指offer刷题笔记》20、调整数组顺序使奇数位于偶数前面【c++详细题解】

我会带着你远行 2021-07-24 16:02 144阅读 0赞

### **题目** ###

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

**样例**

输入：[1,2,3,4,5]
    
    输出: [1,3,5,2,4]

### **思路1** ###

**(枚举)**  O ( n ) O(n) O(n)

定义两个数组，分别记录数组中的奇数和偶数。

**时间复杂度分析**

枚举整个数组,判断每个数是否是奇数或者偶数的时间复杂度为 O ( n ) O(n) O(n)。由于多开了两个数组，这样的做法空间复杂度会变高。

### **代码1** ###

class Solution { 
    public:
        void reOrderArray(vector<int> &array) { 
             vector<int>odd; //奇数
             vector<int>even; //偶数
             for(int i = 0; i < array.size(); i++)
             { 
                 if(array[i]%2) odd.push_back(array[i]);
                 else even.push_back(array[i]);
             }
             for(int i = 0; i < odd.size(); i++) array[i] = odd[i];
             for(int j = 0; j < even.size(); j++) array[odd.size() + j] = even[j];
        }
    };

### **思路2** ###

**(双指针扫描)** O ( n ) O(n) O(n)  
用两个指针分别从首尾开始，往中间扫描。扫描时保证第一个指针前面的数都是奇数，第二个指针后面的数都是偶数。

每次迭代时需要进行的操作：

1.  第一个指针一直往后走，直到遇到第一个偶数为止；
2.  第二个指针一直往前走，直到遇到第一个奇数为止；
3.  交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止；

**时间复杂度**  
当两个指针相遇时，走过的总路程长度是  n n n，所以时间复杂度是  O ( n ) O(n) O(n)。

### **代码2** ###

class Solution { 
    public:
        void reOrderArray(vector<int> &array) { 
             int l = 0, r = array.size() - 1;
             while (l < r) { 
                 while (l < r && array[l] % 2 == 1) l ++ ;
                 while (l < r && array[r] % 2 == 0) r -- ;
                 if (l < r) swap(array[l], array[r]);
             }
        }
    };