做网站商丘,销型网站建设必须的步骤包括,网站html有趣代码,网业游戏大全1. 问题描述
给出2n2个非负整数元素的数组#xff0c;除其中两个数字之外#xff0c;其他每个数字均出现两次#xff0c;找到这两个数字。
2. 问题示例
给出[1#xff0c;2#xff0c;2#xff0c;3#xff0c;4#xff0c;4#xff0c;5#xff0c;3]#xff0c…1. 问题描述
给出2n2个非负整数元素的数组除其中两个数字之外其他每个数字均出现两次找到这两个数字。
2. 问题示例
给出[12234453]返回1和5。
3. 代码实现
使用异或运算实现
def find_two_numbers(nums):xor_result 0for num in nums:xor_result ^ numxor_result -xor_resultnum1, num2 0, 0for num in nums:if num xor_result 0:num1 ^ numelse:num2 ^ numreturn num1, num2# 从输入获取数组
input_str input(请输入数组以逗号分隔)
nums list(map(int, input_str.split(,)))# 调用函数并输出结果
result find_two_numbers(nums)
print(单独出现的两个数字是:, result)
使用异或运算的性质。异或运算具有以下几个性质
a ^ a 0任何数与自身进行异或运算结果为0。a ^ 0 a任何数与0进行异或运算结果为其本身。异或运算满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b。
基于以上性质可以通过遍历数组并依次进行异或运算最后的结果就是那两个单独出现的数字的异或结果。 具体步骤如下 初始化一个变量 xor_result 为0用于存储所有元素的异或结果。遍历数组 nums对每个元素进行异或运算并更新 xor_resultxor_result ^ num。在 xor_result 中找到任意为1的位可以通过 xor_result -xor_result 来实现。初始化两个变量 num1 和 num2 为0用于存储两个单独出现的数字。再次遍历数组 nums对每个元素进行判断 如果 (num xor_result) 0则说明该元素在找到的那一位为0。 对 num1 进行异或运算num1 ^ num。否则说明该元素在找到的那一位为1。 对 num2 进行异或运算num2 ^ num。返回最终结果 (num1, num2)。 这个算法的时间复杂度是 O(n)其中 n 是数组的长度。它需要遍历数组三次一次用于计算异或结果一次用于找到异或结果中为1的位一次用于判断数字分组。异或运算和位运算的时间复杂度都是 O(1)。
