前言
这个题没有太多好说的，但引申出了数值交换问题。
分析题目
评论区给出了两种解法：前后指针、快慢指针
解法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;
}
}
运行结果：
不断调整循环次数，观察结果，发现第三种表现优异，但相差不大。
循环1e8次的结果：
循环1e9次的结果：
