※ 引述《Meaverzt (單推凜寶)》之銘言：
: 題目：
: 有兩個陣列nums1跟nums2裡面有很多數字
: 我們要去做一個nums3裡面是nums1跟nums2中所有xor後可能的值
: 最後回傳nums3每一項xor後的值
: 思路：
: 因為一個數字只要被xor兩次就會變0
: 所以去算每個數字被xor幾次
: 只要是奇數就去跟答案xor
這題是數學問題
暴力解是
for &n1 in &nums1 {
for &n2 in &nums2 {
result ^= (n1 ^ n2);
}
}
但這效率很爛 所以不太可能直接用這個
考慮到結果num3等於所有n1 ^ n2的xor
也就是num3實際上是
(nums1[i] ^ nums2[0]) ^ (nums1[i] ^ nums2[1]) ^ ... ^ (nums1[i] ^ nums2[n-1])
的結果
所以因為大家都是xor
根據分配律
可以改寫成
nums1[i] ^ nums1[i] ^ ... ^ nums1[i] ^ nums2[0] ^ nums2[1] ^ ... ^ nums2[n-1]
然後總之
計算 nums1 的 XOR 和 xor1
計算 nums2 的 XOR 和 xor2
如果 nums2 的長度是奇數 則結果包含 xor1
如果 nums1 的長度是奇數 則結果包含 xor2
Code:
impl Solution {
pub fn xor_all_pairings(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let xor1: i32 = nums1.iter().fold(0, |acc, &x| acc ^ x);
let xor2: i32 = nums2.iter().fold(0, |acc, &x| acc ^ x);
let m = nums1.len();
let n = nums2.len();
let mut result = 0;
if n % 2 == 1 {
result ^= xor1;
}
if m % 2 == 1 {
result ^= xor2;
}
result
}
}