V2EX › ppyybb 的所有回复 › 第 12 页 / 共 16 页

V2EX = way to explore

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

For Existing Member Sign In

1 ... 4 5 6 7 8 9 10 11 12 13 ... 16

❮

❯

2018 年 8 月 18 日

回复了 xe2vherd 创建的主题 › C › 一个简单的数组面试题

@zmxnv123 有些细节没写全哦，但是大概思路应该可以

2018 年 8 月 17 日

回复了 xe2vherd 创建的主题 › C › 一个简单的数组面试题

这样做，从头扫描数组
对于 a[i] = x，
如果 i==x，那么直接下一个
否则，和 a[x]的绝对值比较，如果不等，就进行交换。
如果相等，就代表找到一个重复出现的数字，这时候把数字取反得到负数。
然后继续当前位置，如果数字是 n，就记录到一个单独变量里面（额外的一个空间）。
最后这个数组里面的唯一正数就是答案。

时间复杂度很容易说明，每一次要不前进，要不就交换，而每次交换都会将一个数字放到原本的位置上，所以是 o （ n ）

1 ... 4 5 6 7 8 9 10 11 12 13 ... 16

❮

❯