Python算法例26 落单的数Ⅳ

发布时间:2023年12月24日

1. 问题描述

给定数组,除了一个数出现一次外,所有数都出现两次,并且所有出现两次的数都挨着,找出出现一次的数。

2. 问题示例

给出nums=[3,3,2,2,4,5,5],返回4,4只出现了一次;给出nums=[2,1,1,3,3],返回2,2只出现了一次。

3. 代码实现

使用异或运算实现

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

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

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

具体步骤如下:

  1. 初始化一个变量 result 为0,用于存储所有元素的异或结果。
  2. 遍历数组 nums,对每个元素进行异或运算并更新 result:result ^= num。
  3. 返回 result。
def find_single_number(nums):
    result = 0
    for num in nums:
        result ^= num

    return result

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

# 调用函数并输出结果
result = find_single_number(nums)
print("只出现一次的数字是:", result)

这个算法的时间复杂度是 O(n),其中 n 是数组的长度。它需要遍历数组一次来计算异或结果,异或运算的时间复杂度是 O(1)。

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