今天晚上面试,有一个数组的题。 一个大小为 n 的数组,数组的内容为 1~n 的任意数,这些数中有一个数出现了 1 次,其他数出现 0 次或多次,怎么在 O(n)时间复杂度,O(1)空间复杂度内找到这个出现 1 次的数? 有没有大佬来解释一下?
1
feather12315 2018-08-17 23:27:25 +08:00 via Android
刚刚牛客网上面看到了类似的题目,不过有个限制:数的大小限制在 0-n-1,这题目名称为:数组中重复的数字
|
2
zmxnv123 OP @feather12315 方便给个链接吗
|
3
1423 2018-08-17 23:34:23 +08:00
其他数出现 0 次或多次?不是偶数次?
|
4
qiuqiuer 2018-08-17 23:36:08 +08:00 via Android
每个出现了 1 次?
|
5
wbing 2018-08-17 23:37:35 +08:00
如果其他数是 0 次或偶数次的话,就全部异或一遍,剩下的那个
|
7
dtgio 2018-08-17 23:45:13 +08:00 via iPhone
用 unordered_map 记录每个数出现的次数?
|
8
rabbbit 2018-08-17 23:49:17 +08:00
数组是有序的吗?
|
9
crayygy 2018-08-17 23:50:54 +08:00 via iPhone
异或
|
10
feather12315 2018-08-17 23:59:25 +08:00
|
11
ppyybb 2018-08-17 23:59:40 +08:00 via iPhone 3
这样做,从头扫描数组
对于 a[i] = x, 如果 i==x,那么直接下一个 否则,和 a[x]的绝对值比较,如果不等,就进行交换。 如果相等,就代表找到一个重复出现的数字,这时候把数字取反得到负数。 然后继续当前位置,如果数字是 n,就记录到一个单独变量里面(额外的一个空间)。 最后这个数组里面的唯一正数就是答案。 时间复杂度很容易说明,每一次要不前进,要不就交换,而每次交换都会将一个数字放到原本的位置上,所以是 o ( n ) |
12
innoink 2018-08-18 00:03:38 +08:00 via Android
这就是数据可以当下标用的一个地方
|
15
Daath 2018-08-18 00:48:17 +08:00 via Android
堆排序了解一下
|
16
Mirana 2018-08-18 00:55:27 +08:00
把数字 N 放在数组对应的下标上 Array[N-1]
|
17
zheyu 2018-08-18 01:13:05 +08:00 via Android 1
第一遍遍历把数字 i 放在 a[i-1]上,第二遍遍历对 a[i-1]!=i 的地方,令 a[a[i-1]]=0,第三遍遍历找到 a[i-1]==i 的值。这个 i 应该就是只出现一次的数字了
|
18
wenzhoou 2018-08-18 05:30:54 +08:00 via Android
简单的再开一个数组,记录每个数字出现的次数。然后再遍历一遍,找到次数为 1 的数字。
|
19
l30n 2018-08-18 07:25:53 +08:00 via Android 1
利用原来数组的空间
|
23
XxxxD 2018-08-18 12:09:08 +08:00
python 里面有个 count ()的函数,for in 一遍,找出属于 1 的?
|
24
snail1988 2018-08-18 12:12:27 +08:00
利用固定偏移可以时间复杂度 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; } |
25
wenzhoou 2018-08-18 12:14:23 +08:00 via Android
不能开数组那就是上面说的异或了。
|
26
baelish 2018-08-18 12:14:45 +08:00
遍历第 1 次,A[A[i]] *= n
遍历第 2 次,if(A[i] > n && A[i] < n*n) return A[i]/n |
27
baelish 2018-08-18 12:15:39 +08:00
* 换成 +
|
28
snail1988 2018-08-18 12:16:07 +08:00
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; } |
29
baelish 2018-08-18 12:40:15 +08:00 1
遍历第 1 次,A[A[i]] += n
遍历第 2 次,if(A[i] > n && A[i] < 2*n) return A[i]-n 这回就对了 |
31
ppyybb 2018-08-18 14:10:41 +08:00 via iPhone
@smdbh 真巧,这是我校验的第一个 case。按我的做法最后状态变成-2 1 -2,所以 1 是唯一的。
|
33
sikariba 2018-08-18 14:27:15 +08:00
主楼跟你回复里贴的链接完全就是 2 道题啊。。
|
35
thedog 2018-08-18 15:14:11 +08:00 via Android
异或一把
|
38
vandort 2018-08-18 15:49:12 +08:00
我有个正确却没什么意义的答案:用睡排序对数组进行排序,然后就很好找那个出现了一次的数了
|
39
zmxnv123 OP @所有人 LZ 已经知道正确方法了 感谢各位
|
40
lcj2class 2018-08-19 17:17:39 +08:00
|
41
waytoexplorewhat 2018-08-20 11:19:14 +08:00 via Android
看了评论感觉很乱(楼主也太不负责了,知道答案就跑路了)。说一下自己的思路。如果可以修改原数组的内容,可以在原数组上做统计,m 这个数未出现过记 arr[m]为 0,出现 x 次值则为-x,这样可以通过一次遍历完成统计,再一次遍历找出值为-1 的那个数
|