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

原题链接

题解

快慢指针

定义两个指针i，j分别指向数组的初始，i表示数组中奇数要插入的位置，j向后去找奇数，找到就和i这个位置进行交换

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = 0;//i表示前面奇数的边界
        while(j < nums.length){
            if(nums[j] % 2 == 1) {
              swap(nums, i, j);  
              i ++;
            }
            j ++; 
        }

        return nums;
    }

    void swap(int[] q, int i, int j){
        int t = q[i];
        q[i] = q[j];
        q[j] = t;
    }
}

首尾指针

类似于快排的思想，初始两个指针变量i，j分别指向数组的开始和末端。i向后找偶数，j向前找奇数，如果两者相遇就结束了

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while(i < j){
            while(i < j && (nums[i] & 1) == 1) ++ i;
            while(i < j && (nums[j] & 1) == 0) -- j;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        return nums;
    }
}