题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
解题思路:本题关键之处在于要求奇数、偶数的相对位置不变,因此需要定义一个vector先遍历一遍,把奇数存入,然后再遍历一遍,再存入偶数。
1 class Solution { 2 public: 3 void reOrderArray(vector<int> &array) { 4 int n = array.size(); 5 vector<int> a; 6 for(int i=0;i<n;i++) 7 { 8 if(array[i]&1)//奇数 9 { 10 a.push_back(array[i]); 11 } 12 } 13 for(int i=0;i<n;i++) 14 { 15 if((array[i]&1)==0)//偶数 16 { 17 a.push_back(array[i]); 18 } 19 } 20 for(int i=0;i<a.size();i++) 21 { 22 array[i] = a[i]; 23 } 24 } 25 };
补充:如果不考虑奇数、偶数的相对顺序,可以分别定义left、right从左右开始,当左侧遇到偶数、右侧遇到奇数,进行交换,直到left=right停止,则为结果。
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 class Solution { 6 public: 7 void reOrderArray(vector<int> &array) { 8 int n = array.size(); 9 vector<int> a; 10 for(int i=0;i<n;i++) 11 { 12 if(array[i]&1)//奇数 13 { 14 a.push_back(array[i]); 15 } 16 } 17 for(int i=0;i<n;i++) 18 { 19 if((array[i]&1)==0)//偶数 20 { 21 a.push_back(array[i]); 22 } 23 } 24 for(int i=0;i<a.size();i++) 25 { 26 array[i] = a[i]; 27 } 28 } 29 void reOrderArray2(vector<int> &array) { 30 int left = 0; 31 int n = array.size(); 32 int right = n-1; 33 while(left<right) 34 { 35 while((array[left]&1) == 1) 36 { 37 left++; 38 } 39 while((array[right]&1) == 0)//优先级问题,必须加括号 40 { 41 right--; 42 } 43 if(left < right)//避免进来就是按照奇数、偶数排列的需要至少交换一次的情况 44 { 45 swap(&array[left],&array[right]); 46 left++; 47 right--; 48 } 49 } 50 } 51 void swap(int *a,int *b) 52 { 53 int temp = *a; 54 *a = *b; 55 *b = temp; 56 } 57 }; 58 int main() 59 { 60 vector<int> a; 61 a.push_back(2); 62 a.push_back(3); 63 a.push_back(6); 64 a.push_back(5); 65 a.push_back(7); 66 a.push_back(4); 67 cout<<"原数组为:"<<endl; 68 for(int i=0;i<a.size();i++) 69 { 70 cout<<a[i]<<endl; 71 } 72 Solution s; 73 s.reOrderArray(a); 74 cout<<"考虑奇数、偶数相对顺序结果"<<endl; 75 for(int i=0;i<a.size();i++) 76 { 77 cout<<a[i]<<endl; 78 } 79 s.reOrderArray2(a); 80 cout<<"已经排序好的数组,不考虑奇数、偶数相对顺序结果"<<endl; 81 for(int i=0;i<a.size();i++) 82 { 83 cout<<a[i]<<endl; 84 } 85 a.clear(); 86 a.push_back(2); 87 a.push_back(3); 88 a.push_back(6); 89 a.push_back(5); 90 a.push_back(7); 91 a.push_back(4); 92 s.reOrderArray2(a); 93 cout<<"原数组,不考虑奇数、偶数相对顺序结果"<<endl; 94 for(int i=0;i<a.size();i++) 95 { 96 cout<<a[i]<<endl; 97 } 98 return 0; 99 }