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

mario 2020年09月16日 86次浏览

前言

这个题没有太多好说的,但引申出了数值交换问题。

分析题目

image.png
评论区给出了两种解法:前后指针、快慢指针

解法1 - 前后指针

class Solution {
    //前后双指针解法
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 当找到一个偶数时,就跳出循环。
            // (这里有个求奇偶数的小技巧,就是当一个数是奇数时,它的二进制表示的最后一位肯定是1
            while (left < right && (nums[left] & 1) == 1) {
                left++;
            }
            // 当找到一个奇数时,就跳出循环
            while (left < right && (nums[right] & 1) == 0) {
                right--;
            }
            // 如果两个指针还没有碰到一起时,说明找到了需要交换的位置
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}

解法2 - 快慢指针

class Solution {
     // 快慢指针
     public void exchange(int[] nums) {
         int low = 0, fast = 0, tmp = 0;
         while (fast < nums.length) {
             if ((nums[fast] & 1) == 1) {
                 tmp = nums[fast];
                 nums[fast] = nums[low];
                 nums[low] = tmp;
                 low++;
             }
             fast++;
         }
    }
}

解法3 - 申请额外数组

申请长度为nums.length的数组res,遍历两遍nums,第一遍把奇数塞进res,第二遍把偶数塞进res。

数值交换

可以看到解法1和解法2都需要交换数值的操作。现在用的最广泛的是定义临时变量,而另外两种方法可能不容易想到。老师教过第二种方法,当时没在意( ̄△ ̄;)。至于第三种,看题解时发现的,用异或求出不同的部分,类似于第二种的求和。
比较下三者的效率:

class Solution {
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        for (int i = 0; i < 1e6; i++) {
            swap1(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
        }
        long t2 = System.currentTimeMillis();
        System.out.println("Swap1 takes " + (t2 - t1) + " ms");

        t1 = System.currentTimeMillis();
        for (int i = 0; i < 1e6; i++) {
            swap2(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
        }
        t2 = System.currentTimeMillis();
        System.out.println("Swap2 takes " + (t2 - t1) + " ms");

        t1 = System.currentTimeMillis();
        for (int i = 0; i < 1e6; i++) {
            swap3(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
        }
        t2 = System.currentTimeMillis();
        System.out.println("Swap3 takes " + (t2 - t1) + " ms");
    }

    public static void swap1(int a, int b) {
        int tmp = a;
        a = b;
        b = tmp;
    }

    public static void swap2(int a, int b) {
        a = a + b;
        b = a - b;
        a = a - b;
    }

    public static void swap3(int a, int b) {
	if (a == b) return;
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

运行结果:
image.png
不断调整循环次数,观察结果,发现第三种表现优异,但相差不大。
循环1e8次的结果:
image.png
循环1e9次的结果:
image.png

参考

【题解】:首尾双指针,快慢双指针