一个简单的数组面试题

[zmxnv123]

今天晚上面试，有一个数组的题。 一个大小为 n 的数组，数组的内容为 1~n 的任意数，这些数中有一个数出现了 1 次，其他数出现 0 次或多次，怎么在 O(n)时间复杂度,O(1)空间复杂度内找到这个出现 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