一个简单的数组面试题

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

@feather12315 方便给个链接吗

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

每个出现了 1 次？

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

@1423 对的 不是偶数次

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

数组是有序的吗?

异或

@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) 是相关的讨论

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

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

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

@ppyybb 好像可以 明天试一下

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

堆排序了解一下

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

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

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

利用原来数组的空间

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

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

@ppyybb ,1 2 2 ？

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

利用固定偏移可以时间复杂度 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;
}

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

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

* 换成 +

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;
}

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

这回就对了

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

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

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

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

@likers 你说的正确。

异或一把

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

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

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

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

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