V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zmxnv123
V2EX  ›  C

一个简单的数组面试题

  •  1
     
  •   zmxnv123 · 2018-08-17 23:25:04 +08:00 · 5310 次点击
    这是一个创建于 2291 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天晚上面试,有一个数组的题。 一个大小为 n 的数组,数组的内容为 1~n 的任意数,这些数中有一个数出现了 1 次,其他数出现 0 次或多次,怎么在 O(n)时间复杂度,O(1)空间复杂度内找到这个出现 1 次的数? 有没有大佬来解释一下?

    41 条回复    2018-08-20 11:19:14 +08:00
    feather12315
        1
    feather12315  
       2018-08-17 23:27:25 +08:00 via Android
    刚刚牛客网上面看到了类似的题目,不过有个限制:数的大小限制在 0-n-1,这题目名称为:数组中重复的数字
    zmxnv123
        2
    zmxnv123  
    OP
       2018-08-17 23:30:55 +08:00
    @feather12315 方便给个链接吗
    1423
        3
    1423  
       2018-08-17 23:34:23 +08:00
    其他数出现 0 次或多次?不是偶数次?
    qiuqiuer
        4
    qiuqiuer  
       2018-08-17 23:36:08 +08:00 via Android
    每个出现了 1 次?
    wbing
        5
    wbing  
       2018-08-17 23:37:35 +08:00
    如果其他数是 0 次或偶数次的话,就全部异或一遍,剩下的那个
    zmxnv123
        6
    zmxnv123  
    OP
       2018-08-17 23:41:34 +08:00
    @1423 对的 不是偶数次
    dtgio
        7
    dtgio  
       2018-08-17 23:45:13 +08:00 via iPhone
    用 unordered_map 记录每个数出现的次数?
    rabbbit
        8
    rabbbit  
       2018-08-17 23:49:17 +08:00
    数组是有序的吗?
    crayygy
        9
    crayygy  
       2018-08-17 23:50:54 +08:00 via iPhone
    异或
    ppyybb
        11
    ppyybb  
       2018-08-17 23:59:40 +08:00 via iPhone   ❤️ 3
    这样做,从头扫描数组
    对于 a[i] = x,
    如果 i==x,那么直接下一个
    否则,和 a[x]的绝对值比较,如果不等,就进行交换。
    如果相等,就代表找到一个重复出现的数字,这时候把数字取反得到负数。
    然后继续当前位置,如果数字是 n,就记录到一个单独变量里面(额外的一个空间)。
    最后这个数组里面的唯一正数就是答案。

    时间复杂度很容易说明,每一次要不前进,要不就交换,而每次交换都会将一个数字放到原本的位置上,所以是 o ( n )
    innoink
        12
    innoink  
       2018-08-18 00:03:38 +08:00 via Android
    这就是数据可以当下标用的一个地方
    zmxnv123
        13
    zmxnv123  
    OP
       2018-08-18 00:11:19 +08:00 via Android
    @ppyybb 好像可以 明天试一下
    ppyybb
        14
    ppyybb  
       2018-08-18 00:12:18 +08:00 via iPhone
    @zmxnv123 有些细节没写全哦,但是大概思路应该可以
    Daath
        15
    Daath  
       2018-08-18 00:48:17 +08:00 via Android
    堆排序了解一下
    Mirana
        16
    Mirana  
       2018-08-18 00:55:27 +08:00
    把数字 N 放在数组对应的下标上 Array[N-1]
    zheyu
        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 应该就是只出现一次的数字了
    wenzhoou
        18
    wenzhoou  
       2018-08-18 05:30:54 +08:00 via Android
    简单的再开一个数组,记录每个数字出现的次数。然后再遍历一遍,找到次数为 1 的数字。
    l30n
        19
    l30n  
       2018-08-18 07:25:53 +08:00 via Android   ❤️ 1
    利用原来数组的空间
    daozhihun
        20
    daozhihun  
       2018-08-18 08:03:53 +08:00 via Android
    @wenzhoou 空间要求为 1,不能开数组
    snail1988
        21
    snail1988  
       2018-08-18 10:48:44 +08:00
    @ppyybb 你这样有个前提是必须有序,否则就是 log 级别的时间复杂度
    smdbh
        22
    smdbh  
       2018-08-18 11:26:06 +08:00
    @ppyybb , 1 2 2 ?
    XxxxD
        23
    XxxxD  
       2018-08-18 12:09:08 +08:00
    python 里面有个 count ()的函数,for in 一遍,找出属于 1 的?
    snail1988
        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;
    }
    wenzhoou
        25
    wenzhoou  
       2018-08-18 12:14:23 +08:00 via Android
    不能开数组那就是上面说的异或了。
    baelish
        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
    baelish
        27
    baelish  
       2018-08-18 12:15:39 +08:00
    * 换成 +
    snail1988
        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;
    }
    baelish
        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

    这回就对了
    ppyybb
        30
    ppyybb  
       2018-08-18 14:05:22 +08:00 via iPhone
    @snail1988 显然不用,这题我做过....
    ppyybb
        31
    ppyybb  
       2018-08-18 14:10:41 +08:00 via iPhone
    @smdbh 真巧,这是我校验的第一个 case。按我的做法最后状态变成-2 1 -2,所以 1 是唯一的。
    likers
        32
    likers  
       2018-08-18 14:11:59 +08:00
    @wenzhoou 其他数字是出现 0 或多次,不是偶数次,不能异或
    sikariba
        33
    sikariba  
       2018-08-18 14:27:15 +08:00
    主楼跟你回复里贴的链接完全就是 2 道题啊。。
    wenzhoou
        34
    wenzhoou  
       2018-08-18 14:58:53 +08:00 via Android
    @likers 你说的正确。
    thedog
        35
    thedog  
       2018-08-18 15:14:11 +08:00 via Android
    异或一把
    snail1988
        36
    snail1988  
       2018-08-18 15:14:21 +08:00
    @ppyybb 如果最坏情况 你相当于要把一半的元素进行交换排序
    snail1988
        37
    snail1988  
       2018-08-18 15:16:44 +08:00
    @ppyybb 又想了一下,这个排序相当于桶排序,是 O(n)的 那总体复杂度确实还是 O(n)
    vandort
        38
    vandort  
       2018-08-18 15:49:12 +08:00
    我有个正确却没什么意义的答案:用睡排序对数组进行排序,然后就很好找那个出现了一次的数了
    zmxnv123
        39
    zmxnv123  
    OP
       2018-08-18 21:13:57 +08:00 via Android
    @所有人 LZ 已经知道正确方法了 感谢各位
    lcj2class
        40
    lcj2class  
       2018-08-19 17:17:39 +08:00
    waytoexplorewhat
        41
    waytoexplorewhat  
       2018-08-20 11:19:14 +08:00 via Android
    看了评论感觉很乱(楼主也太不负责了,知道答案就跑路了)。说一下自己的思路。如果可以修改原数组的内容,可以在原数组上做统计,m 这个数未出现过记 arr[m]为 0,出现 x 次值则为-x,这样可以通过一次遍历完成统计,再一次遍历找出值为-1 的那个数
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3449 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 11:39 · PVG 19:39 · LAX 03:39 · JFK 06:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.