Python算法例25 落单的数Ⅲ

2023-12-24 07:12
文章标签 python 算法 25 落单

本文主要是介绍Python算法例25 落单的数Ⅲ,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 问题描述

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

2. 问题示例

给出[1,2,2,3,4,4,5,3],返回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)

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

  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)。

这篇关于Python算法例25 落单的数Ⅲ的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/530966

相关文章

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

Python办公自动化实战之打造智能邮件发送工具

《Python办公自动化实战之打造智能邮件发送工具》在数字化办公场景中,邮件自动化是提升工作效率的关键技能,本文将演示如何使用Python的smtplib和email库构建一个支持图文混排,多附件,多... 目录前言一、基础配置:搭建邮件发送框架1.1 邮箱服务准备1.2 核心库导入1.3 基础发送函数二、

Python包管理工具pip的升级指南

《Python包管理工具pip的升级指南》本文全面探讨Python包管理工具pip的升级策略,从基础升级方法到高级技巧,涵盖不同操作系统环境下的最佳实践,我们将深入分析pip的工作原理,介绍多种升级方... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核