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

剑指offer刷题笔记：21. 调整数组顺序使奇数位于偶数前面

题目描述

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

示例

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

解题思路1 头尾指针

记录这题是因为这是最近leetcode第一道没有出现错误一气呵成的题目，算是一个小小的里程碑吧。虽然很简单，但是给了我信心哈哈。
算法很简单，首先创建一个新数组，然后遍历原数组，遇到奇数放到头上，遇到偶数放到尾巴上。

代码

class Solution {
    public int[] exchange(int[] nums) {
        // new一个新数组
        int[] res = new int[nums.length];

        // 确定新数组的头和尾的位置
        int h = 0;
        int t = nums.length - 1;

        // 遍历nums，如果为奇数则放入新数组头的位置，否则放入新数组尾巴的位置
        for(int i = 0; i < nums.length; i++){
            if(nums[i] % 2 == 1){
                res[h] = nums[i];
                h++;
            }else{
                res[t] = nums[i];
                t--;
            }
        }
        return res;
    }
}

解题思路2 原数组上交换

因为解题思路1的内存消耗较大，所以想到在原数组上互换。
结果内存消耗从49.4MB变为47.6MB，超越人数从2%提升到90%。
但是执行用时从超越99%的2ms变为超越34.3%的3ms。

代码

class Solution {
    public int[] exchange(int[] nums) {
        int head = 0;
        int tail = nums.length - 1;

        // if-else的顺序十分巧妙
        // 先判断头尾是否符合要求，如果前两个if都走完了说明两个都不符合要求，则互换
        while(head <= tail){
            if(nums[head] % 2 == 1){
                head++;
            }else if(nums[tail] % 2 == 0){
                tail--;
            }else{
                int tmp = nums[head];
                nums[head] = nums[tail];
                nums[tail] = tmp;

                head++;
                tail--;
            }
        }
        return nums;
    }
}