找单独的数

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。

要求:

1. 设计一个算法，使其时间复杂度为 O(n)，其中 n 是班级的人数。
2. 尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1：

输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2：

输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：拿到数字 2 的同学是唯一一个没有配对的。

解题思路

1. 初始化一个变量 result = 0。
2. 遍历数组 cards，对于每个元素 card，执行异或操作 result ^= card。异或操作具有交换律和结合律，因此可以保证最终 result 的值为那个单独的数字。
3. 返回 result。

代码实现

Cangjie

func solution(cards: Array<Int64>): Int64{
    var result = 0
    for (card in cards) {
        result ^= card
    }
    result
}

main(){
    println(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
    println(solution([0, 1, 0, 1, 2]) == 2)   
}

Rust

fn solution(cards: Vec<i32>) -> i32 {
    let mut result = 0;
    for card in cards {
        result ^= card;
    }
    result
}

fn main() {
   println!("{}", solution(vec![1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4);
   println!("{}", solution(vec![0, 1, 0, 1, 2]) == 2);
}

Python

def solution(cards):
    result = 0
    for card in cards:
        result ^= card
    return result

print(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4)
print(solution([0, 1, 0, 1, 2]) == 2)

JavaScript

function solution(cards) {
    let result = 0;
    for (let card of cards) {
        result ^= card
    }
    return result
}

console.log(solution([1, 1, 2, 2, 3, 3, 4, 5, 5]) == 4);
console.log(solution([0, 1, 0, 1, 2]) == 2);

复杂度分析

1. 时间复杂度：O(n)，其中 n 是班级的人数。遍历数组一次，异或操作的时间复杂度为 O(1)。
2. 空间复杂度：O(1), 只使用了常数级别的额外空间。