Jianzhi offer interview question 14: Adjust the order of the array so that the odd number is in front of the even number (C++ version)_Adjust the position of the array that can be divisible by 3 in the front_Broad sea sky1992’s blog

Title: Input an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array.

Thinking Analysis:

You can maintain two pointers i and j, i points to the first number of the array, it only moves backward; j points to the last number of the array, it only moves forward. The first pointer is always in front of the second pointer until the two pointers meet. If the number pointed to by the first pointer is even and the number pointed to by the second pointer is odd, swap the two numbers. When the two pointers meet, it means that all the odd numbers are already in front of the even numbers.

Time complexity: O(n)

Code:

#include 
 #include 
 using namespace std;

 vector & func(vector &a){
 vector :: iterator i = a.begin();
 vector :: iterator j = a.end() - 1;//end points to the next position of the end element

 while(i < j){
 while( i != j && (*i & 1) == 1 ){//Odd number, move the i pointer backward until it points to an even number
 i++;
 }
 while( i != j && (*j & 1) == 0){//even number, move the j pointer forward until it points to an odd number
 j --;
 }
 if( i < j){//exchange two pointers
 int tmp = *i;
 *i = *j;
 *j = tmp;
 }
 }
 return a;
 }

 int main