[已解决]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

def test(nums):
    length = len(nums)
    result = []

    if length < 2:
        print('error nums...')
        return result

    nums.sort()
    i = 0
    while i < length-1:
        if nums[i] == nums[i+1]:
            i+=2
            if i == length - 1:
                result.append(nums[i])
        else:
            result.append(nums[i])
            i+=1
    return result

nums = [-5, 1, 6, -3, 6, -3, 1, 10]
list1 = test(nums)
print(list1)

跳转到最佳答案楼层

yuedong

def findone(str):
    str2 = []
    for each1 in str:
        count = 0
        for each2 in str:
            if each1 == each2:
                count += 1
        if count == 1:
            str2.append(each1)
    print(str2)
a = [4,6,4,2]
findone(a)

isZz

def findNum(nums):
    dt = dict()
    for i in nums:
        dt[i] = dt.get(i,0) + 1
    return [k for k,v in dt.items() if v == 1]

print(findNum([4,1,4,6]))

coolsummer2080

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

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

coolsummer2080

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

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

crisfo

def test(nums):
    length = len(nums)
    result = []

    if length < 2:
        print('error nums...')
        return result

    nums.sort()
    i = 0
    while i < length-1:
        if nums[i] == nums[i+1]:
            i+=2
            if i == length - 1:
                result.append(nums[i])
        else:
            result.append(nums[i])
            i+=1
    return result

nums = [-5, 1, 6, -3, 6, -3, 1, 10]
list1 = test(nums)
print(list1)

yuedong

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

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

yuedong

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

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

yuedong

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

def findone(str):
    a = str
    b = []
    for i in a:
        n = a.count(i)
        if n ==1:
            b.append(i)
    print(b)
nums = [4,6,4,2]
findone(nums)

z5560636

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

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

atai0622

def fun1(nums):
    result=[]
    for each in nums:
        if nums.count(each)==1:
            result.append(each)
    return result

nums=[1,2,10,4,1,4,3,3]
print(fun1(nums))

isZz

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

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

coolsummer2080

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

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

z5560636

def num(nums):
    nums = sorted(nums)
    i = 0
    while i <= 2:
        if i < len(nums)-1 and not nums[i] ^ nums[i+1] :
            nums.remove(nums[i])
            nums.remove(nums[i])
            i -=1
        i += 1
    return nums

print(num([4,1,4,6]))
print(num([1,2,10,4,1,4,3,3]))

z5560636

在优化一下...

def num(nums):
    nums = sorted(nums)
    i = 0
    while i < 2:
        if i < len(nums)-1 and not nums[i] ^ nums[i+1] :
            nums.remove(nums[i])
            nums.remove(nums[i])
            i -=1
        i += 1

    if len(nums) >2:
        return nums[0:2]
    return nums

print(num([4,1,4,6]))
print(num([1,2,10,4,1,4,3,3]))
print(num([1,2,3,3,4,4,5,5]))

liuzhengyuan

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

qq1151985918

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

atai0622

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

atai0622

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

def num(nums):
    nums = sorted(nums)
    i = 0
    while i < 2:
        if i < len(nums)-1 and not nums[i] ^ nums[i+1] :     #请教一下，后半句nums[i]^nums[i+1]的作用是什么？
            nums.remove(nums[i])
            nums.remove(nums[i])
            i -=1
        i += 1

    if len(nums) >2:
        return nums[0:2]
    return nums

print(num([4,1,4,6]))
print(num([1,2,10,4,1,4,3,3]))
print(num([1,2,3,3,4,4,5,5]))

qq1151985918

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

def find(nums):
    return [x for x in nums if nums.count(x) == 1]

lst = [1,2,3,4,5,6,7,8,3,4,5,6,7,8]
print(find(lst))