网站开发图片压缩,郑州网站建设推荐美软科技,长沙线上引流公司,网上最好购物网站描述#xff1a; 一个整型数组里除了两个数字只出现一次#xff0c;其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 要求#xff1a;空间复杂度 O(1)#xff0c;时间复杂度O(n)。 题目传送门 is here
思路#xff1a;
方法一#xff1a;最简单的思路就… 描述 一个整型数组里除了两个数字只出现一次其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 要求空间复杂度 O(1)时间复杂度O(n)。 题目传送门 is here
思路
方法一最简单的思路就是使用字典记录每个数的出现次数最后再遍历一遍字典出现次数为1的数。空间复杂度 O(n)时间复杂度O(n)。空间复杂度不满足题目条件。
:)小妙招使用字典的mydict[key] mydict.get(key, 0)函数可以轻松将字典不存在的值设置为初始值0。
方法二还是要用一个字典记录但是如果出现第二次就remove掉因此最后字典就只剩下出现一次的数值。空间复杂度 O(n)时间复杂度O(n)。空间复杂度不满足题目条件。
基础知识 使用mydict.get(key)获取key值无就会返回None。
方法三利用 异或 和 与 运算。
假设只出现一次的数为ab。 大体思路分为三个步骤 步骤一 整个数组的数都异或一遍最终的值为c a^b。 步骤二 打住先花30秒思考如何利用c来得出a和b …1s… …2s… …3s… . . …30s… okk 想到了吗反正我没想到。[尬住哈]
答案还记得异或特点是不同为1吗a, b 两个不同的数异或出来肯定会有至少某一位数是1。对吧。 上栗子 100 ^ 110 010 中间那位不一样 001 ^ 100 101 头尾两位不一样。 所以我们可以利用c 中为1的那一位用来区分出 a 和 b。 具体做法就是找为1的那一位将整个数组分成两组数一组含a和重复数 另一组含b和重复数。 至此橘事已定。 步骤三 最后梅开二度再来一遍异或。分别对这两组数进行异或运算最终得出一组异或值为a, 另一组的异或值为b。
回忆那死去的数学 异或特点就是两个相同的数异或结果为0a ^ a 0 相互抵消掉了。一个数异或0结果不变。 b ^ 0 b 因此1 ^ 1 ^ 4 4 与操作特点相同为1不同为0可以区分某个位上是0还是1。举个栗子使用001分别与上000, 001, 010, 011 可以将一组数区分成000、010 和 001,011两组数这两组数的特点是最后一位不相同。
代码
#from typing import List
class Solution:# 方法一 count每个数的次数def FindNumsAppearOnce1(self , nums: List[int]) - List[int]:# write code herecnt {}for item in nums:cnt[item] cnt.get(item, 0) 1print(cnt)result []for k ,v in cnt.items():if v 1:result.append(k)return sorted(result)# 方法二出现过就removedef FindNumsAppearOnce2(self , nums: List[int]) - List[int]:# write code herecnt {}for item in nums:if cnt.get(item) None:cnt[item] 1else:del cnt[item]result []for k,_ in cnt.items():result.append(k)return sorted(result)# 方法三使用异或def FindNumsAppearOnce(self , nums: List[int]) - List[int]:# 步骤一全部异或一遍tmp nums[0]for i in range(1,len(nums)):tmp tmp ^ nums[i]print(tmp)# 步骤二得出只有两个数得异或之后从低位开始选择第一个为1的那位可以对这两个数进行分组group_num 1while group_num tmp 0:group_num group_num 1print(bin(group_num))# 步骤三进行分组group1 ,group2 0,0list1 ,list2 [],[] # 这两个list只是拿来看看分组情况,最后[1,4,1,6] 会分成 [1,4,1] [6]for item in nums:if item group_num 0:list1.append(item)group1 group1^item # 对组1的数进行异或else:list2.append(item)group2 group2^item # 对组2的数进行异或print(group: ,list1, list2)if group1 group2:return [group2, group1]else:return [group1, group2]#so Solution()
#exp1 [1,4,1,6]
#print(so.FindNumsAppearOnce(exp1)) 昨天做的题今天写个博客梳理一下。方法三里面考到的数学知识已经忘了复习起来花了不少时间。本来用方法一和方法二就能通过了觉得方法三没必要了。但是仔细一看空间复杂度居然是O(1) 那方法一、二的空间复杂度是O(n)老不达标了。 牛客网放我过了但是比赛或者面试的oj就没有那么仁慈了。因此还是要重视起时间复杂度和空间复杂度。有一位比赛大佬和我说有时候呢可以从这个时间复杂度还有数组的规模来判断用的是什么解法。比如时间复杂度为1s数组长度10^9次方。那肯定只能遍历一遍数组了于是乎两层for循环那肯定过不了的。
