这是一个创建于 2309 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天晚上面试，有一个数组的题。 一个大小为 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 的那个数
|
Select Language