题目
封装两个函数，分别完成下面的编码任务。
（1）在一个整型数组中，数字都是两两相同，只有一个不同，请编写代码，最快找出这个不同的数字。
（2）在一个整型数组中，数字都是两两相同，只有两个不同，请编写代码，最快找出这两个不同的数字。
解析
我们先看第一道小题，初看题目，觉得不难。遍历数组两遍，不就能找到那个不同的数字了吗？但题目中提到“最快”，当前遍历数组的方法显然并不高效。那么，有更快的方法找出这个不同的数字吗？
我们可以思考一下异或运算的特点：两个相同的数异或为0，两个不同的数异或不为0，与0异或值不变。另外，异或还满足交换律，a^b^c与a^c^b的值相等。根据这个特点，我们将数组中的所有数字异或一遍：两两相同的数异或为0，0与不同的那个数异或，最终结果即为要找的那个数。根据这个思路，我们给出了第一道小题的示例代码。
pub fn find_not_repeating_number(numbers: &[i32]) -> i32 {
let mut result = 0;
for &num in numbers {
result ^= num;
}
result
}
fn main() {
let numbers1 = vec![26, 15, 32, 88, 26, 32, 88];
let unique1 = find_not_repeating_number(&numbers1);
println!("{}", unique1);
let numbers2 = vec![100, 24, 36, 87, 87, 56, 36, 100, 24];
let unique2 = find_not_repeating_number(&numbers2);
println!("{}", unique2);
}
我们再来看第二道小题，与第一道小题不同，数组中有两个不同的数字了，怎么办呢？我们可以猜测一下出题者的出题意图，先出了简单一点的第一小题，然后出了难一点的第二小题，这是否是在暗示我们：第二小题需要根据第一小题的解题思路，再深入思考呢？
实际上，有了第一小题的结论，我们可以考虑能否将这个数组划分成两个数组，使每个数组中各包含一个只出现了一次的数字。由于有两个数字只出现了一次，故将所有数异或后，结果肯定不为0，其二进制表示中至少有一位为1。可以依据这一位是否相同，将原数组划分成两个数组，从而直接套用第一小题的结论来解题。
下面，我们给出了第二道小题的示例代码。
pub fn find_two_not_repeating_numbers(numbers: &[i32]) -> (i32, i32) {
let mut xor_result = 0;
// 得到所有整数的异或值
for &num in numbers {
xor_result ^= num;
}
// 找到最右边不是0的那一位
let rightmost_set_bit = xor_result & (!xor_result + 1);
let mut num1 = 0;
let mut num2 = 0;
// 根据这一位是否为0，分成两组进行异或
for &num in numbers {
if (num & rightmost_set_bit) != 0 {
num1 ^= num;
} else {
num2 ^= num;
}
}
(num1, num2)
}
fn main() {
let numbers1 = vec![26, 15, 32, 88, 26, 100, 32, 88];
let (unique1, unique2) = find_two_not_repeating_numbers(&numbers1);
println!("{}, {}", unique1, unique2);
let numbers2 = vec![100, 24, 36, 87, 87, 63, 56, 36, 100, 24];
let (unique3, unique4) = find_two_not_repeating_numbers(&numbers2);
println!("{}, {}", unique3, unique4);
}
总结
通过这道题，我们学习了异或运算的特点，并利用该特点，找出了数组中不同的数。在第二道小题中，我们采用了“分而治之”的思想，将原数组从逻辑上划分成了两个数组，从而顺利找到了两个不同的数。
推荐链接
发表评论