剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com)

    /**
     * 会有 O(N) 的空间复杂度
     */
//    public int[] exchange(int[] nums) {
        int[] ans = nums; 这样是不行的，会有bug，估摸着是地址相同了
//        int[] ans = new int[nums.length];
//        int left = 0;
//        int right = nums.length - 1;
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] % 2 != 0) {
//                ans[left++] = nums[i];
//            } else {
//                ans[right--] = nums[i];
//            }
//        }
//        return ans;
//    }

    /**
     *  O(1) 的空间复杂度
     */
    public int[] exchange(int[] nums) {
        int tmp;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && (nums[left] & 1) == 1) {
                left++;
            }
            while (left < right && (nums[right] & 1) == 0) {
                right--;
            }
            tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
        return nums;
    }