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

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/

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)