HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

leetcode——找单独的数

7
0
0
2025-03-11

leetcode——找单独的数

问题描述

在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小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 只出现一次，是独特的卡片。

样例3：

输入：cards = [7, 3, 3, 7, 10]
输出：10
解释：10 是班级中唯一一个不重复的数字卡片。

约束条件

  • 1 ≤ cards.length ≤ 1001

  • 0 ≤ cards[i] ≤ 1000

  • 班级人数为奇数

  • 除了一个数字卡片只出现一次外，其余每个数字卡片都恰好出现两次

代码

def solution(cards):
    # Edi your code here
    result=0
    for  i in cards :
        result^=i
    return result

if __name__ == "__main__":
    # Add your test cases here
    cards=[1, 1, 2, 2, 3, 3, 4, 5, 5]
    print(solution(cards))

知识点

异或运算（XOR）具有以下几个特性：

  1. 相同为0，不同为1：对于两个相同的数字，异或运算的结果是0。例如，5 ^ 5 = 0。

  2. 与0异或保持不变：任何数字与0进行异或运算，结果仍然是该数字本身。例如，5 ^ 0 = 5。

  3. 交换律和结合律：异或运算满足交换律和结合律，即 a ^ b ^ c = a ^ c ^ b。

基于这些特性，我们可以利用异或运算来找到数组中唯一的那个数字。具体步骤如下：

  1. 初始化一个变量 result 为0。

  2. 遍历数组中的每一个元素，将 result 与当前元素进行异或运算。

  3. 最终 result 的值就是那个唯一的数字。

解释

  • 由于数组中除了一个数字外，其他数字都出现了两次，因此这些成对的数字在异或运算中会相互抵消，结果为0。

  • 唯一出现一次的数字与0进行异或运算后，结果仍然是该数字本身。

因此，通过遍历整个数组并进行异或运算，最终得到的 result 就是那个唯一的数字。

示例

假设数组为 [1, 1, 2, 2, 3, 3, 4, 5, 5]：

  • result = 0

  • result = 0 ^ 1 = 1

  • result = 1 ^ 1 = 0

  • result = 0 ^ 2 = 2

  • result = 2 ^ 2 = 0

  • result = 0 ^ 3 = 3

  • result = 3 ^ 3 = 0

  • result = 0 ^ 4 = 4

  • result = 4 ^ 5 = 1

  • result = 1 ^ 5 = 4

最终 result 的值为 4，即数组中唯一的数字。