面试题21. 调整数组顺序使奇数位于偶数前面

面试题21. 调整数组顺序使奇数位于偶数前面

Scroll Down

调整数组顺序使奇数位于偶数前面

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

示例:

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

思路

双指针,一个从前向后找到第一个偶数,另一个从后向前找到第一个奇数,然后交换。

解答

class Solution {
    public int[] exchange(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        
        int p1 = 0, p2 = nums.length - 1;
        while (p1 < p2) {
            while (p1 < p2 && (nums[p1]&1) == 1) p1++;
            while (p1 < p2 && (nums[p2]&1) == 0) p2--;

            int tmp = nums[p1];
            nums[p1] = nums[p2];
            nums[p2] = tmp;
        }
        return nums;
    }
}