Skip to content

Files

Latest commit

author
pezy
Sep 10, 2018
feaec0b · Sep 10, 2018

History

History
This branch is up to date with pezy/LeetCode:master.

435. Find All Duplicates in an Array

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Sep 10, 2018
Sep 10, 2018
Sep 10, 2018

这道题一定要审题,LeetCode 的特点是,题目言简意赅。那么就一定要从字字品味,获取思路。

首先,拿到这道题,如果没有这俩限制,是相当简单的:

  1. without extra space
  2. O(n) runtime

其一不让你多用空间,其二只允许一次遍历。这还让不让人活了?算法不就是空间与时间的游戏吗?俩都不让步,怎么玩。

沮丧之余,只好再多读几遍题。终于发现有几个奇怪的设定:

  1. some elements appear twice and others appear once
  2. 1 <= a[i] <= n (n = size of array)

其一,简化场景,数组里要么出现两次,要么出现一次。其二,数组里的数字,肯定大于等于 1,并小于等于数组长度

这时候该笑出声了,暗示的不能再明显了。不让你用多余的空间,因为数组里的数,可以无缝转化为 index. 不让你用多余的时间,因为要么两次,要么一次,一次迭代完全足够了。

既然数组里每一个数字,都可以映射为 index(这个 index 可以想象成坑位),那么我们就得想,怎么对坑位做个标记,知道这个坑位已经来过人了。

这个标记,你大可以按自己喜好来,就是个简单的加密解密思维,取余?+n/-n?都可以,这里最直观的标记,是正负号。为什么呢?因为数字肯定大于1,那么一定是正数,如果出现负数,就可以证明该坑位被用过。

于是这道所谓 Medium 的题,就成了 easy 档次的,3行就搞定了:

int index = abs(nums[i]) - 1;
if (nums(index) < 0) ret.push_back(index + 1);
nums[index] = -nums[index];