leetcode 第 42 期竞赛的第一题, 看到个非常巧妙的解法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2681 天前的主题，其中的信息可能已经有所发展或是发生改变。

https://leetcode.com/contest/leetcode-weekly-contest-42/problems/set-mismatch/
(需要登录才能看到,所以转载下题目)

645. Set Mismatch

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

The given array size will in the range [2, 10000]. The given array's numbers won't have any order.

下面是解法

class Solution(object):
    def findErrorNums(self, nums):
        t1 = sum(nums)
        t2 = sum(set(nums))
        l = len(nums)
        return [t1 - t2, l * (l + 1) / 2 - t2]

排名第四好像还是个学生

PS: 如果有兴趣和时间做题这期第四题用正则表达式解也挺有趣的 https://leetcode.com/contest/leetcode-weekly-contest-42/problems/replace-words/

第 1 条附言 · 2017-07-23 14:34:59 +08:00

问题被添加了不用登录也可以看到了

https://leetcode.com/problems/replace-words/#/description

7 条回复 • 2017-07-24 11:47:21 +08:00

huntzhan

2017-07-23 14:06:39 +08:00

这个解法很常规呀，空间复杂度 O(n)。
你要不要思考下 O(1) 的解法......

zongwan

2017-07-23 14:25:11 +08:00

这个是我的...
```
class Solution:
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
nums.sort()
last = 0
res_1, res_2 = None, None
# print(nums)
for i in nums:
if not res_1 and i == last:
res_1 = last
elif not res_2 and last + 1 != i:
res_2 = last + 1
last = i
if res_1 and res_2:
break
res_2 = res_2 if res_2 else (nums[-1] + 1)
return [res_1, res_2]
```

这个是其他人普通的
class Solution(object):
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = [0, 0]
cnt = [0] * len(nums)
for i in nums:
cnt[i-1] += 1
for i in xrange(len(nums)):
if cnt[i] == 0:
ans[1] = i+1
elif cnt[i] == 2:
ans[0] = i+1
return ans

@huntzhan
排行榜上大部分都清一色是普通的那种算法
我也不知道自己的算不算 O(1)