关于leetcode:每日一练11调整数组顺序使奇数位于偶数前面

title: 每日一练（11）：调整数组程序使奇数位于偶数后面

categories:[剑指 offer]

tags:[每日一练]

date: 2022/01/24

每日一练（11）：调整数组程序使奇数位于偶数后面

输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有奇数在数组的前半部分，所有偶数在数组的后半局部。

示例：

输出：nums = [1,2,3,4]

输入：[1,3,2,4]

注：[3,1,2,4] 也是正确的答案之一。

提醒：

0 <= nums.length <= 50000

0 <= nums[i] <= 10000

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：有手就行

建设容器，第一次循环放入奇数，第二次循环放入偶数 .

vector<int> exchange(vector<int>& nums) {
    vector<int>res;
    for (int i = 0; i < nums.size(); i++) {if ((nums[i] & 1) != 0) {//nums[i] & 1) != 0 可用 nums[i] % 2 代替
            res.push_back(nums[i]);    // 放入奇数
        } 
    }
    for (int i = 0; i < nums.size(); i++) {if ((nums[i] & 1) != 1) {//nums[i] & 1) != 0 可用 (nums[i] % 2) == 0 代替
            res.push_back(nums[i]);    // 放入偶数
        } 
    }
    return res;
}

办法二：首尾双指针

• 定义头指针 left，尾指针 right .
• left 始终往右移，直到它指向的值为偶数 .
• right 始终往左移，直到它指向的值为奇数 .
• 替换 nums[left] 和 nums[right] .
• 反复上述操作，直到 left == right .

vector<int> exchange(vector<int>& nums) {int left = 0, right = nums.size() - 1;
    while (left < right) {if ((nums[left] & 1) != 0) {    // 如果为偶数
            left++;
            continue;
        }
        if ((nums[right] & 1) != 1) {    // 如果为奇数
            right--;
            continue;
        }
        swap(nums[left++], nums[right--]);    // 替换值
    }
    return nums;
}

办法三：快慢双指针

• 定义快慢双指针 fast 和 slow，fast 在前，slow 在后 .
• fast 的作用是向前搜寻奇数地位，slow 的作用是指向下一个奇数该当寄存的地位 .
• fast 向前挪动，当它搜寻到奇数时，将它和 nums[slow] 替换，此时 slow 向前挪动一个地位 .
• 反复上述操作，直到 fast 指向数组开端 .

vector<int> exchange(vector<int>& nums) {
    int slow = 0, fast = 0;
    while (fast < nums.size()) {if ((nums[fast]) & 1) { // 奇数
            swap(nums[slow], nums[fast]);// 替换
            slow++;
        }
        fast++;
    }
    return nums;
}