这是一个创建于 2678 天前的主题，其中的信息可能已经有所发展或是发生改变。
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
 |
1
huntzhan 2017-07-23 14:06:39 +08:00
这个解法很常规呀，空间复杂度 O(n)。
你要不要思考下 O(1) 的解法...... |
 |
2
zongwan OP 这个是我的...
``` 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) |
 |
3
jadetang 2017-07-23 14:28:01 +08:00 via Android
O N 的算法不算巧妙吧
|
 |
5
andyhuzhill 2017-07-23 22:01:43 +08:00
@zongwan 你这里面不是有一个 for 循环遍历元素了么 不就是 O(n)的了么？
|
 |
7
anthow 2017-07-24 11:47:21 +08:00
高中生做这样的题目妥妥的 : )
|
Select Language