一个简单的数组面试题

[zmxnv123]

今天晚上面试，有一个数组的题。 一个大小为 n 的数组，数组的内容为 1~n 的任意数，这些数中有一个数出现了 1 次，其他数出现 0 次或多次，怎么在 O(n)时间复杂度,O(1)空间复杂度内找到这个出现 1 次的数? 有没有大佬来解释一下?

[feather12315]

刚刚牛客网上面看到了类似的题目，不过有个限制：数的大小限制在 0-n-1，这题目名称为：数组中重复的数字

[zmxnv123]

@feather12315 方便给个链接吗

[1423]

其他数出现 0 次或多次？不是偶数次？

[qiuqiuer]

每个出现了 1 次？

[wbing]

如果其他数是 0 次或偶数次的话，就全部异或一遍，剩下的那个

[zmxnv123]

@1423 对的 不是偶数次

[dtgio]

用 unordered_map 记录每个数出现的次数？

[rabbbit]

数组是有序的吗?

[crayygy]

异或

[feather12315]

@zmxnv123 #2 [数组中重复的数字]( https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
[这里]( https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8) 是相关的讨论

[ppyybb]

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

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

[innoink]

这就是数据可以当下标用的一个地方

[zmxnv123]

@ppyybb 好像可以 明天试一下

[ppyybb]

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

[Daath]

堆排序了解一下

[Mirana]

把数字 N 放在数组对应的下标上 Array[N-1]

[zheyu]

第一遍遍历把数字 i 放在 a[i-1]上，第二遍遍历对 a[i-1]!=i 的地方，令 a[a[i-1]]=0，第三遍遍历找到 a[i-1]==i 的值。这个 i 应该就是只出现一次的数字了

[wenzhoou]

简单的再开一个数组，记录每个数字出现的次数。然后再遍历一遍，找到次数为 1 的数字。

[l30n]

利用原来数组的空间

[daozhihun]

@wenzhoou 空间要求为 1，不能开数组