输入一个整数数组, 实现一个函数来调整该数组中数字的顺序, 使得所有的奇数位于数组的前半部分, 所有的偶数位于数组的后半部分,
并保证奇数和奇数, 偶数和偶数之间的相对位置不变.
思路一: // 冒泡排序法, 如果两个相邻的是前偶后奇数, 就交换 O(n^2)
代码:
- #include <iostream>
- #include <vector>
- using namespace std;
- class Solution {
- public:
- // 冒泡排序法, 如果两个相邻的是前偶后奇数, 就交换
- void reOrderArray(vector<int> &array)
- {
- vector<int> arr2;
- int len = array.size();
- for(int i = 0; i <len; i++)
- {
- for(int j = 0; j < len-1; j++)
- {
- if (array[j] % 2 == 0 && array[j+1] % 2 != 0)
- {
- int temp = array[j];
- array[j] = array[j+1];
- array[j+1] = temp;
- }
- }
- }
- }
- };
- int main()
- {
- Solution s;
- vector<int> vec = {3,4,5,1,2};
- s.reOrderArray(vec);
- for(int i = 0; i<vec.size(); i++)
- {
- cout << vec[i]<<" ";
- }
- return 0;
- }
思路二: O(n) 但是用了一个辅助数组, 牺牲空间换取时间效率
- // 利用一个辅助数组, 先把奇数放进去, 然后把偶数放进去, 最后把辅助数组的值拷贝给原数组
- #include <iostream>
- #include <vector>
- using namespace std;
- class Solution {
- public:
- // 利用一个辅助数组, 先把奇数放进去, 然后把偶数放进去, 最后把辅助数组的值拷贝给原数组
- void reOrderArray(vector<int> &array)
- {
- vector<int> arr2;
- int len = array.size();
- for( int i = 0; i <len; i++)
- {
- if (array[i] % 2 != 0)
- arr2.push_back(array[i]);
- }
- for( int i = 0; i < len; i++)
- {
- if (array[i] % 2 == 0)
- arr2.push_back(array[i]);
- }
- for(int i = 0; i< arr2.size(); i++)
- {
- array[i] = arr2[i];
- }
- // 也可以进行赋值
- // array.assign(arr2.begin(),arr2.end());
- }
- };
- int main()
- {
- Solution s;
- vector<int> vec = {3,4,5,1,2};
- s.reOrderArray(vec);
- for(int i = 0; i< vec.size(); i++)
- {
- cout << vec[i]<<" ";
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3452573.html