一个简单的数组面试题

[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，不能开数组

[snail1988]

@ppyybb 你这样有个前提是必须有序，否则就是 log 级别的时间复杂度

[smdbh]

@ppyybb , 1 2 2 ？

[XxxxD]

python 里面有个 count （）的函数，for in 一遍，找出属于 1 的？

[snail1988]

利用固定偏移可以时间复杂度 O(n),空间 O(1) 下面贴一段 demo，没处理 数组 size 接近 int 极限的情况

int unique_number(int arr[], int n) {
for (int idx = 0; idx < n; ++idx) {
int i = (abs(arr[idx])%n?:n)-1;
if (arr[i] > 0) {
arr[i] = -arr[i];
}
else if (arr[i] < 0) {
arr[i] = arr[i] - n;
}
}
for (int idx = 0; idx < n; ++idx) {
if (arr[idx] < 0 && arr[idx] > -n) {
return idx+1;
}
}
return 0;
}

[wenzhoou]

不能开数组那就是上面说的异或了。

[baelish]

遍历第 1 次，A[A[i]] *= n
遍历第 2 次，if(A[i] > n && A[i] < n*n) return A[i]/n

[baelish]

* 换成 +

[snail1988]

sorry，少写了一等号

int unique_number(int arr[], int n) {
for (int idx = 0; idx < n; ++idx) {
int i = (abs(arr[idx])%n?:n)-1;
if (arr[i] > 0) {
arr[i] = -arr[i];
}
else if (arr[i] < 0) {
arr[i] = arr[i] - n;
}
}
for (int idx = 0; idx < n; ++idx) {
if (arr[idx] < 0 && arr[idx] >= -n) {
return idx+1;
}
}
return 0;
}

[baelish]

遍历第 1 次，A[A[i]] += n
遍历第 2 次，if(A[i] > n && A[i] < 2*n) return A[i]-n

这回就对了

[ppyybb]

@snail1988 显然不用，这题我做过....

[ppyybb]

@smdbh 真巧，这是我校验的第一个 case。按我的做法最后状态变成-2 1 -2，所以 1 是唯一的。

[likers]

@wenzhoou 其他数字是出现 0 或多次，不是偶数次，不能异或

[sikariba]

主楼跟你回复里贴的链接完全就是 2 道题啊。。

[wenzhoou]

@likers 你说的正确。

[thedog]

异或一把

[snail1988]

@ppyybb 如果最坏情况 你相当于要把一半的元素进行交换排序

[snail1988]

@ppyybb 又想了一下，这个排序相当于桶排序，是 O(n)的 那总体复杂度确实还是 O(n)

[vandort]

我有个正确却没什么意义的答案：用睡排序对数组进行排序，然后就很好找那个出现了一次的数了

[zmxnv123]

@所有人 LZ 已经知道正确方法了 感谢各位

[lcj2class]

https://gitee.com/liujiacai/codes/gieq2j9vhy71srduakzb427

[waytoexplorewhat]

看了评论感觉很乱（楼主也太不负责了，知道答案就跑路了）。说一下自己的思路。如果可以修改原数组的内容，可以在原数组上做统计，m 这个数未出现过记 arr[m]为 0，出现 x 次值则为-x，这样可以通过一次遍历完成统计，再一次遍历找出值为-1 的那个数