题目描述

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

示例

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

算法思路

思路一

采用左右双指针的技巧：

定义左指针left，右指针right
左指针一直往右移，直到所指的数是偶数
右指针一直往左移，直到所指的数是奇数
交换nums[left]和nums[right]
直到 left == right 为止

思路二

采用快慢双指针的技巧

定义low = fast = 0
fast 一直向前搜索奇数的位置，low则是下一个奇数要存放的位置。
当 fast 搜索到奇数时，交换和 low 的位置，low++
直到 fast 指向数组末尾

代码实现

实现一

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            //如果是奇数，一直往右移
            if((nums[left]&1)==1){
                left++;
                continue;
            }
            //如果是偶数，一直往左移
            if((nums[right]&1)==0){
                right--;
                continue;
            }
            //左指针碰到偶数，右指针碰到奇数，交换
            swap(nums,left++,right--);
        }
        return nums;
    }

    private void swap(int[]nums,int a,int b){
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

实现二

class Solution {
    public int[] exchange(int[] nums) {
        int low = 0;
        int fast = 0;
        while(fast<nums.length){
            //如果快指针所指的是奇数，交换和low所指的位置
            if((nums[fast]&1)==1){
                swap(nums,low,fast);
                low++;
            }
            //fast一直向前搜索，碰到奇数就交换
            fast++;
        }
        return nums;

    }

    private void swap(int[]array,int a,int b){
        int c = array[a];
        array[a] = array[b];
        array[b] = c;
    }
}

题目改进

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例

输入：[2,4,6,5,7]
返回值：[5,7,2,4,6]
注：[7,5,6,4,2]不是正确答案

题目这样一改就不能使用双指针了，因为使用双指针的话，他们的相对位置就会改变

我这里采用的思路是：

使用两个存储结构，一个存储奇数，一个存储偶数
指针向前移动，碰到奇数，就把奇数存储到奇数的数据结构里，碰到偶数就存储到偶数的数据结构里
最后把偶数的数据结构拼接到奇数的数据结构里

代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] odd = new int[array.length];
        ArrayList<Integer> even = new ArrayList<>();
        int j = 0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0){
                even.add(array[i]);
            }else{
                odd[j] = array[i];
                j++;
            }
        }
        
        for(int i=0;i<even.size();i++){
            odd[j] = even.get(i);
            j++;
        }
        
        return odd;
    }
}