字节面试官: 先出道简单的考考你

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public int[] exchange(int[] nums) {

        // 定义头指针 left 
        int left = 0 ;
 
        // 定义尾指针 right 
        int right = nums.length - 1;

        // 定义临时变量 tmp 
        int tmp;
        
        // 移动 left 和 right ，直到 left 在 right 右侧或者相遇为止
        while(left < right) {

            // 如果 left 指针指向的元素值是奇数，那么说明该元素在左侧了，观察其它的元素，即让 left 向右移动
            while(left < right && (nums[left] & 1) == 1) left++;

            // 如果 right 指针指向的元素值是偶数，那么说明该元素在右侧了，观察其它的元素，即让 right 向左移动
            while(left < right && (nums[right] & 1) == 0) right--;

            // 否则就说明，此时要么 left 指向的元素值为偶数，要么 right 指向的元素值为奇数
            // 交换这两个位置的元素
            tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

        // 最后返回结果就行
        return nums;
    }
}