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

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

难度简单 84

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

示例：

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

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

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

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while(i < j) &#123;
            while(i < j && (nums[i] & 1) == 1) i++;
            System.out.println("i="+i+",j="+j);
            while(i < j && (nums[j] & 1) == 0) j--;
            System.out.println("i="+i+",j="+j);
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        &#125;
        return nums;
    &#125;

// 作者：jyd
// 链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4/

&#125;

---

好理解，浪费空间

class Solution {
    public int[] exchange(int[] nums) {
        int[] res = new int[nums.length];
        int left = 0;
        int right = nums.length-1;

        int k =0;
        while(k<nums.length)&#123;
            //奇数
            if((nums[k]&1)==1 )&#123;
                res[left++] = nums[k];
            &#125;
            else&#123;
                res[right--] = nums[k];
            &#125;
            k++;
        &#125;
        return res;
    &#125;

&#125;

---

    public int[] exchange(int[] nums) {
        int p = 0;
        int len = nums.length;
        for(int i = 0; i < len; i ++)&#123;
            if((nums[i]&1)==1)&#123;
                int tmp = nums[i];
                nums[i] = nums[p];
                nums[p++] = tmp;
            &#125;
        &#125;
        return nums;
    &#125;
作者：xmblgt
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/zhe-dao-ti-you-you-rang-wo-xiang-qi-liao-gczhong-d/

解析

只有遍历到的 nums[i]全为奇数时，p 和 i 保持相同大小，如果遇到偶数元素，那么 i 直接跳过继续 i++,而 p 则会停留在为偶数元素的位置上，这也是为什么要 nums[i]和 nums[p]互换，只有这样才能在一次遍历中把奇数元素位置的元素变为偶数。