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

[zongwan]

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/

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

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

[huntzhan]

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

[zongwan]

这个是我的...
```
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)

[jadetang]

O N 的算法不算巧妙吧

[CYKun]

@zongwan 你这有排序就不可能 O(1)的

[andyhuzhill]

@zongwan 你这里面不是有一个 for 循环遍历元素了么　不就是 O(n)的了么？

[mkdong]

@CYKun 人家说 O1 是指空间复杂度

[anthow]

高中生做这样的题目妥妥的 : )