剑指Offer(五十):数组中重复的数字

2018年1月21日10:28:30 4 1,001 °C
摘要

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

剑指Offer(五十):数组中重复的数字

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

1、思路

还可以把当前序列当成是一个下标和下标对应值是相同的数组(时间复杂度为O(n),空间复杂度为O(1)); 遍历数组,判断当前位的值和下标是否相等:

  • 若相等,则遍历下一位;
  • 若不等,则将当前位置i上的元素和a[i]位置上的元素比较:若它们相等,则找到了第一个相同的元素;若不等,则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的,但i位置上的元素和下标并不一定对应;重复2的操作,直到当前位置i的值也为i,将i向后移一位,再重复2。

本文采用思路3,如果还是不懂,看下面的实例分析就懂了!

举例说明:{2,3,1,0,2,5,3}

  • 0(索引值)和2(索引值位置的元素)不相等,并且2(索引值位置的元素)和1(以该索引值位置的元素2为索引值的位置的元素)不相等,则交换位置,数组变为:{1,3,2,0,2,5,3};
  • 0(索引值)和1(索引值位置的元素)仍然不相等,并且1(索引值位置的元素)和3(以该索引值位置的元素1为索引值的位置的元素)不相等,则交换位置,数组变为:{3,1,2,0,2,5,3};
  • 0(索引值)和3(索引值位置的元素)仍然不相等,并且3(索引值位置的元素)和0(以该索引值位置的元素3为索引值的位置的元素)不相等,则交换位置,数组变为:{0,1,2,3,2,5,3};
  • 0(索引值)和0(索引值位置的元素)相等,遍历下一个元素;
  • 1(索引值)和1(索引值位置的元素)相等,遍历下一个元素;
  • 2(索引值)和2(索引值位置的元素)相等,遍历下一个元素;
  • 3(索引值)和3(索引值位置的元素)相等,遍历下一个元素;
  • 4(索引值)和2(索引值位置的元素)不相等,但是2(索引值位置的元素)和2(以该索引值位置的元素2为索引值的位置的元素)相等,则找到了第一个重复的元素。

2、代码

C++:

Python:

个人感觉最优的方法:题目里写了数组里数字的范围保证在0 ~ n-1 之间,所以可以利用现有数组设置标志,当一个数字被访问过后,可以设置对应位上的数 + n,之后再遇到相同的数时,会发现对应位上的数已经大于等于n了,那么直接返回这个数即可。

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  2   博主  2

    • avatar easy 来自天朝的朋友 谷歌浏览器 Windows 10 中国 移动 1

      博主,您好,我很看好这个最优的方法,但是当第一个重复的数是0的时候,答案就会出错

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

          @easy 举个输入例子?我测试了一下,没有报错啊。

        • avatar easy 来自天朝的朋友 谷歌浏览器 Windows 10 河北省 移动 1

          运行最优的算法,数列为 1, 3, 2, 0, 0, 2, 5, 3 时,输出的是1而不是0
          个人认为代码 duplication[0] = numbers[index] – n
          这行代码应该改为 duplication[0] = index,结果就对了。

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

              @easy 感谢,已经更正两个错误:第一你说的这里,还有一个判断条件应该是>=n。