Python算法例25 落单的数Ⅲ

2023-12-24 06:40:57

1. 问题描述

给出2n+2个非负整数元素的数组,除其中两个数字之外,其他每个数字均出现两次,找到这两个数字。

2. 问题示例

给出[1,2,2,3,4,4,5,3],返回1和5。

3. 代码实现

使用异或运算实现

def find_two_numbers(nums):
    xor_result = 0
    for num in nums:
        xor_result ^= num

    xor_result &= -xor_result

    num1, num2 = 0, 0
    for num in nums:
        if num & xor_result == 0:
            num1 ^= num
        else:
            num2 ^= num

    return num1, num2

# 从输入获取数组
input_str = input("请输入数组,以逗号分隔:")
nums = list(map(int, input_str.split(',')))

# 调用函数并输出结果
result = find_two_numbers(nums)
print("单独出现的两个数字是:", result)

使用异或运算的性质。异或运算具有以下几个性质:

  1. a ^ a = 0,任何数与自身进行异或运算结果为0。
  2. a ^ 0 = a,任何数与0进行异或运算结果为其本身。
  3. 异或运算满足交换律和结合律:a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。

基于以上性质,可以通过遍历数组并依次进行异或运算,最后的结果就是那两个单独出现的数字的异或结果。

具体步骤如下:

  1. 初始化一个变量 xor_result 为0,用于存储所有元素的异或结果。
  2. 遍历数组 nums,对每个元素进行异或运算并更新 xor_result:xor_result ^= num。
  3. 在 xor_result 中找到任意为1的位,可以通过 xor_result &= -xor_result 来实现。
  4. 初始化两个变量 num1 和 num2 为0,用于存储两个单独出现的数字。
  5. 再次遍历数组 nums,对每个元素进行判断:
    • 如果 (num & xor_result) == 0,则说明该元素在找到的那一位为0。
      对 num1 进行异或运算:num1 ^= num。
    • 否则,说明该元素在找到的那一位为1。
      对 num2 进行异或运算:num2 ^= num。
  6. 返回最终结果 (num1, num2)。

?这个算法的时间复杂度是 O(n),其中 n 是数组的长度。它需要遍历数组三次:一次用于计算异或结果,一次用于找到异或结果中为1的位,一次用于判断数字分组。异或运算和位运算的时间复杂度都是 O(1)。

文章来源:https://blog.csdn.net/m0_62110645/article/details/135171876
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。