[已解决]Python：【新】每日一题 2

liuzhengyuan

专辑说明（积分规则）

今天的题目：

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

请封装成一个函数，nums 为参数

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

2 <= nums.length <= 10000

欢迎大家来答题

来源：力扣（LeetCode）

最佳答案

月排行榜 / 总排行榜

crisfo

2021-3-19 10:00:52

1. def test(nums):
   
2.     length = len(nums)
   
3.     result = []
   
4. 
   
5.     if length < 2:
   
6.         print('error nums...')
   
7.         return result
   
8. 
   
9.     nums.sort()
   
10.     i = 0
    
11.     while i < length-1:
    
12.         if nums[i] == nums[i+1]:
    
13.             i+=2
    
14.             if i == length - 1:
    
15.                 result.append(nums[i])
    
16.         else:
    
17.             result.append(nums[i])
    
18.             i+=1
    
19.     return result
    
20. 
    
21. nums = [-5, 1, 6, -3, 6, -3, 1, 10]
    
22. list1 = test(nums)
    
23. print(list1)

复制代码

跳转到最佳答案楼层

yuedong

1. 
   
2. def findone(str):
   
3.     str2 = []
   
4.     for each1 in str:
   
5.         count = 0
   
6.         for each2 in str:
   
7.             if each1 == each2:
   
8.                 count += 1
   
9.         if count == 1:
   
10.             str2.append(each1)
    
11.     print(str2)
    
12. a = [4,6,4,2]
    
13. findone(a)
    

复制代码

isZz

1. def findNum(nums):
   
2.     dt = dict()
   
3.     for i in nums:
   
4.         dt[i] = dt.get(i,0) + 1
   
5.     return [k for k,v in dt.items() if v == 1]
   
6. 
   
7. print(findNum([4,1,4,6]))

复制代码

coolsummer2080

isZz 发表于 2021-3-19 00:49

空间复杂度是不是不符合题目要求？要求空间复杂度不随数据量增加而变化：O（1）。但是你使用了字典，字典的大小会随着你的输入数据量增加而增大。

coolsummer2080

yuedong 发表于 2021-3-19 00:32

对字符串进行了嵌套循环，时间复杂度符合题目要求么？

crisfo

1. def test(nums):
   
2.     length = len(nums)
   
3.     result = []
   
4. 
   
5.     if length < 2:
   
6.         print('error nums...')
   
7.         return result
   
8. 
   
9.     nums.sort()
   
10.     i = 0
    
11.     while i < length-1:
    
12.         if nums[i] == nums[i+1]:
    
13.             i+=2
    
14.             if i == length - 1:
    
15.                 result.append(nums[i])
    
16.         else:
    
17.             result.append(nums[i])
    
18.             i+=1
    
19.     return result
    
20. 
    
21. nums = [-5, 1, 6, -3, 6, -3, 1, 10]
    
22. list1 = test(nums)
    
23. print(list1)

复制代码

yuedong

coolsummer2080 发表于 2021-3-19 08:54
对字符串进行了嵌套循环，时间复杂度符合题目要求么？

嗯，我才去了解了一下时间复杂度与空间复杂度，我再想想

yuedong

coolsummer2080 发表于 2021-3-19 08:49
空间复杂度是不是不符合题目要求？要求空间复杂度不随数据量增加而变化：O（1）。但是你使用了字典，字典 ...

那他给的就是一个列表，本身空间复杂度不就不是O(1)了？

yuedong

如果有数组不影响空间复杂度的话，我觉得这次应该可以了
只有一个循环了

1. 
   
2. def findone(str):
   
3.     a = str
   
4.     b = []
   
5.     for i in a:
   
6.         n = a.count(i)
   
7.         if n ==1:
   
8.             b.append(i)
   
9.     print(b)
   
10. nums = [4,6,4,2]
    
11. findone(nums)
    

复制代码

z5560636

yuedong 发表于 2021-3-19 10:53
如果有数组不影响空间复杂度的话，我觉得这次应该可以了
只有一个循环了

实际上这个是个算法题目，并不是方法题，要是再加上一条，每个元素只允许访问一次，你怎么破？

atai0622

1. def fun1(nums):
   
2.     result=[]
   
3.     for each in nums:
   
4.         if nums.count(each)==1:
   
5.             result.append(each)
   
6.     return result
   
7. 
   
8. nums=[1,2,10,4,1,4,3,3]
   
9. print(fun1(nums))

复制代码

isZz

coolsummer2080 发表于 2021-3-19 08:49
空间复杂度是不是不符合题目要求？要求空间复杂度不随数据量增加而变化：O（1）。但是你使用了字典，字典 ...

对算法还无系统了解,先抛砖引玉

coolsummer2080

yuedong 发表于 2021-3-19 10:49
那他给的就是一个列表，本身空间复杂度不就不是O(1)了？

给的列表应该不包括再内，题意是不是说的你自己用的空间应该是一个常量。

z5560636

1. def num(nums):
   
2.     nums = sorted(nums)
   
3.     i = 0
   
4.     while i <= 2:
   
5.         if i < len(nums)-1 and not nums[i] ^ nums[i+1] :
   
6.             nums.remove(nums[i])
   
7.             nums.remove(nums[i])
   
8.             i -=1
   
9.         i += 1
   
10.     return nums
    
11. 
    
12. print(num([4,1,4,6]))
    
13. print(num([1,2,10,4,1,4,3,3]))

复制代码

z5560636

在优化一下...

1. def num(nums):
   
2.     nums = sorted(nums)
   
3.     i = 0
   
4.     while i < 2:
   
5.         if i < len(nums)-1 and not nums[i] ^ nums[i+1] :
   
6.             nums.remove(nums[i])
   
7.             nums.remove(nums[i])
   
8.             i -=1
   
9.         i += 1
   
10. 
    
11.     if len(nums) >2:
    
12.         return nums[0:2]
    
13.     return nums
    
14. 
    
15. print(num([4,1,4,6]))
    
16. print(num([1,2,10,4,1,4,3,3]))
    
17. print(num([1,2,3,3,4,4,5,5]))

复制代码

liuzhengyuan

-------------------------分割线--------------------

qq1151985918

1. lst = [1,2,3,4,5,6,7,8,3,4,5,6,7,8]
   
2. print([x for x in lst if lst.count(x) == 1])
   

复制代码

atai0622

运算时间如何缩短？有没有大佬推荐点链接学习学习？我的代码运行时间是9388ms，最低的大佬只用44ms，差在哪了？要显著提高效率，主要关注的点有哪些？

atai0622

z5560636 发表于 2021-3-20 01:21
在优化一下...

1. def num(nums):
   
2.     nums = sorted(nums)
   
3.     i = 0
   
4.     while i < 2:
   
5.         if i < len(nums)-1 and not nums[i] ^ nums[i+1] :     #请教一下，后半句nums[i]^nums[i+1]的作用是什么？
   
6.             nums.remove(nums[i])
   
7.             nums.remove(nums[i])
   
8.             i -=1
   
9.         i += 1
   
10. 
    
11.     if len(nums) >2:
    
12.         return nums[0:2]
    
13.     return nums
    
14. 
    
15. print(num([4,1,4,6]))
    
16. print(num([1,2,10,4,1,4,3,3]))
    
17. print(num([1,2,3,3,4,4,5,5]))

复制代码

qq1151985918

我都搞不清楚了，这个题不是很简单吗？怎么搞的这么复杂的样子？难道是我没理解？

1. def find(nums):
   
2.     return [x for x in nums if nums.count(x) == 1]
   
3. 
   
4. lst = [1,2,3,4,5,6,7,8,3,4,5,6,7,8]
   
5. print(find(lst))
   

复制代码