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

难度

简单

思路

方法一：头尾双指针

剑指offset21.gif

  • 定义两个指针 leftIndex 和 rightIndex，leftIndex 表示左边的偶数，rightIndex 表示右边的奇数。 ```java // 在while循环中不断变化index // 这种写法需要非常注意指针边界， class Solution { public int[] exchange(int[] nums) {

    1.   int length = nums.length;
    2.   if (length == 0) return new int[0];
    3.   int leftIndex = 0;
    4.   int rightIndex = length - 1;
    5.   int temp = -1;
    6.   while (rightIndex > leftIndex) {
    7.       // 左边找到奇数就++
    8.       while ((nums[leftIndex] & 1) == 1 && leftIndex < length - 1) {
    9.           leftIndex++;
    10.       }
    12.       // 右连找到偶数就--
    13.       // 如果不加rightIndex > leftIndex，会造成两边刚好擦肩而过的情况
    14.       // 需要避免右指针超过左指针
    15.       while ((nums[rightIndex] & 1) == 0 && rightIndex > 0 && rightIndex > leftIndex) {
    16.           rightIndex --;
    17.       }
    19.       temp = nums[leftIndex];
    20.       nums[leftIndex] = nums[rightIndex];
    21.       nums[rightIndex] = temp;
    22.   }
    23.   return nums;

    } }

class Solution { public int[] exchange(int[] nums) { if (nums.length == 0) return new int[0]; int leftIndex = 0; int rightIndex = nums.length - 1; while (rightIndex > leftIndex) { // 左边找到奇数就++ if ((nums[leftIndex] & 1) == 1) { leftIndex++; continue; }

        // 右连找到偶数就--
        if ((nums[rightIndex] & 1) == 0) {
            rightIndex --;
            continue;
        }

        // 满足条件，进行交换
        int temp = nums[leftIndex];
        nums[leftIndex++] = nums[rightIndex];
        nums[rightIndex--] = temp;
    }
    return nums;
}

}

| 时间复杂度 | _**O(n)**_ |
| --- | --- |
| 空间复杂度 | _**O(1)**_ |

<a name="9XY3L"></a>
## 

- <br />
| 时间复杂度 | _**O(n)**_ |
| --- | --- |
| 空间复杂度 | _**O(1)**_ |

<a name="XC55m"></a>
# 总结
#

```scala
class Solution {
    public int[] exchange(int[] nums) {
        int length = nums.length;
        if (length == 0) return new int[0];
        int leftIndex = 0;
        int rightIndex = length - 1;
        int temp = -1;
        while (rightIndex > leftIndex) {
            // 左边找到奇数就++
            while ((nums[leftIndex] & 1) == 1 && leftIndex < length - 1) {
                leftIndex++;
            }

            // 右连找到偶数就--
            while ((nums[rightIndex] & 1) == 0 && rightIndex > 0 && rightIndex > leftIndex) {
                rightIndex --;
            }

            temp = nums[leftIndex];
            nums[leftIndex] = nums[rightIndex];
            nums[rightIndex] = temp;
        }
        return nums;
    }
}