剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int[] exchange(int[] nums) {
        List ji = new ArrayList<>();
        List ou = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++){
            if (nums[i] % 2 == 0) ou.add(nums[i]);
            else ji.add(nums[i]);
        }

        ji.addAll(ou);

        int[] res = new int[ji.size()];

        for (int i = 0; i < ji.size(); i++) res[i] = ji.get(i);
        return res;
    }
}

和快速排序的思想有点像：

1、左指针指向处理好的末端
2、右指针指向没有处理好的

class Solution {
    public int[] exchange(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];

        int l = 0, r = n - 1;

        while (l < r){
            while (l < r && nums[l] % 2 != 0) l++;
            while (l < r && nums[r] % 2 == 0) r--;

            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        return nums;
    }
}