Adjust the array order so that the odd number precedes the even number

Categories: [sword refers to offer]

Tags: Daily Practice

date: 2022/01/24

Adjust the order of the array so that the odd number precedes the even number

Take 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 last half of the array.

Example:

Input: nums = [1,2,3,4]

Output:,3,2,4 [1]

[3,1,2,4] is also one of the correct answers.

Tip:

0 <= nums.length <= 50000

0 <= nums[i] <= 10000

Source: LeetCode

Link: leetcode-cn.com/problems/di…

Method one: have a hand on the line

Create a container that loops in odd numbers the first time and even numbers the second time.

vector<int> exchange(vector<int>& nums) {
    vector<int>res;
    for (int i = 0; i < nums.size(a); i++) {if ((nums[i] & 1) != 0) {   //nums[i] & 1) ! Nums [I] % 2
            res.push_back(nums[i]); // put an odd number}}for (int i = 0; i < nums.size(a); i++) {if ((nums[i] & 1) != 1) {   //nums[i] & 1) ! (nums[I] % 2) == 0
            res.push_back(nums[i]); // Put an even number}}return res;
}
Copy the code

Method two: double Pointers at both ends

  • Define head pointer left and tail pointer right.
  • Left keeps moving to the right until it points to even values.
  • Right keeps moving to the left until it points to an odd number.
  • Swap nums[left] and NUMs [right].
  • Repeat until left == right.
vector<int> exchange(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        if ((nums[left] & 1) != 0) {    // If it is even
            left++;
            continue;
        }
        if ((nums[right] & 1) != 1) {   // If it is odd
            right--;
            continue;
        }
        swap(nums[left++], nums[right--]);  / / exchange value
    }
    return nums;
}
Copy the code

Method three: fast and slow double pointer

  • Double Pointers fast and slow are defined, with fast before and slow after.
  • Fast searches forward for odd numbers, and slow points to where the next odd number should be stored.
  • Fast moves forward, and when it searches for an odd number, it swaps it with NUMs [slow], at which point slow moves forward one position.
  • Repeat until fast points to the end of the array.
vector<int> exchange(vector<int>& nums) {
    int slow = 0, fast = 0;
    while (fast < nums.size()) {
        if ((nums[fast]) & 1) { / / odd
            swap(nums[slow], nums[fast]);/ / exchange
            slow++;
        }
        fast++;
    }
    return nums;
}
Copy the code