封装两个函数,分别完成下面的编码任务。
(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); }
通过这道题,我们学习了异或运算的特点,并利用该特点,找出了数组中不同的数。在第二道小题中,我们采用了“分而治之”的思想,将原数组从逻辑上划分成了两个数组,从而顺利找到了两个不同的数。