今天晚上面试，有一个数组的题。 一个大小为 n 的数组，数组的内容为 1~n 的任意数，这些数中有一个数出现了 1 次，其他数出现 0 次或多次，怎么在 O(n)时间复杂度,O(1)空间复杂度内找到这个出现 1 次的数? 有没有大佬来解释一下?
This topic created in 3009 days ago, the information mentioned may be changed or developed.
 |
feather12315Aug 17, 2018 via Android
1
刚刚牛客网上面看到了类似的题目，不过有个限制：数的大小限制在 0-n-1，这题目名称为：数组中重复的数字
|
 |
2
@feather12315 方便给个链接吗
|
 |
slowmanAug 17, 2018
3
其他数出现 0 次或多次？不是偶数次？
|
 |
qiuqiuerAug 17, 2018 via Android
4
每个出现了 1 次？
|
 |
benson458Aug 17, 2018
5
如果其他数是 0 次或偶数次的话，就全部异或一遍，剩下的那个
|
 |
dtgioAug 17, 2018 via iPhone
7
用 unordered_map 记录每个数出现的次数？
|
 |
rabbbitAug 17, 2018
8
数组是有序的吗?
|
 |
crayygyAug 17, 2018 via iPhone
9
异或
|
|
feather12315Aug 17, 2018
10
|
 |
11
这样做，从头扫描数组
对于 a[i] = x， 如果 i==x，那么直接下一个 否则，和 a[x]的绝对值比较，如果不等，就进行交换。 如果相等，就代表找到一个重复出现的数字，这时候把数字取反得到负数。 然后继续当前位置，如果数字是 n，就记录到一个单独变量里面（额外的一个空间）。 最后这个数组里面的唯一正数就是答案。 时间复杂度很容易说明，每一次要不前进，要不就交换，而每次交换都会将一个数字放到原本的位置上，所以是 o （ n ） |
3 |
innoinkAug 18, 2018 via Android
12
这就是数据可以当下标用的一个地方
|
 |
TheGonGAug 18, 2018 via Android
15
堆排序了解一下
|
 |
MiranaAug 18, 2018
16
把数字 N 放在数组对应的下标上 Array[N-1]
|
 |
17
第一遍遍历把数字 i 放在 a[i-1]上，第二遍遍历对 a[i-1]!=i 的地方，令 a[a[i-1]]=0，第三遍遍历找到 a[i-1]==i 的值。这个 i 应该就是只出现一次的数字了
|
 |
wenzhoouAug 18, 2018 via Android
18
简单的再开一个数组，记录每个数字出现的次数。然后再遍历一遍，找到次数为 1 的数字。
|
 |
19
利用原来数组的空间
|
 |
XxxxDAug 18, 2018
23
python 里面有个 count （）的函数，for in 一遍，找出属于 1 的？
|
 |
snail1988Aug 18, 2018
24
利用固定偏移可以时间复杂度 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; } |
|
wenzhoouAug 18, 2018 via Android
25
不能开数组那就是上面说的异或了。
|
 |
baelishAug 18, 2018
26
遍历第 1 次，A[A[i]] *= n
遍历第 2 次，if(A[i] > n && A[i] < n*n) return A[i]/n |
|
baelishAug 18, 2018
27
* 换成 +
|
|
snail1988Aug 18, 2018
28
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
遍历第 1 次，A[A[i]] += n
遍历第 2 次，if(A[i] > n && A[i] < 2*n) return A[i]-n 这回就对了 |
 |
sikaribaAug 18, 2018
33
主楼跟你回复里贴的链接完全就是 2 道题啊。。
|
 |
thedogAug 18, 2018 via Android
35
异或一把
|
 |
vandortAug 18, 2018
38
我有个正确却没什么意义的答案：用睡排序对数组进行排序，然后就很好找那个出现了一次的数了
|
|
39
@所有人 LZ 已经知道正确方法了 感谢各位
|
 |
waytoexplorewhatAug 20, 2018 via Android
41
看了评论感觉很乱（楼主也太不负责了，知道答案就跑路了）。说一下自己的思路。如果可以修改原数组的内容，可以在原数组上做统计，m 这个数未出现过记 arr[m]为 0，出现 x 次值则为-x，这样可以通过一次遍历完成统计，再一次遍历找出值为-1 的那个数
|
Select Language