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

  • A+
所属分类:剑指Offer
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

思路1:

如果先排序,再找出重复的数字是一件很容易的事情,只需要从头到尾遍历排序后的数组就可以了。排序一个长度为n的数组需要O(nlogn)的时间。

思路2:

还可以利用hash表来解决这个问题,从头到尾按顺序扫描数组中的每个数,每扫描到一个数字的时候,都可以用O(1)的时间来判断哈希表里是否已经包含了该数字。如果哈希表里还没有这个数字,就把它加入到哈希表中;如果已经存在,就说明找到了一个重复的数字。算法复杂度为O(n),但是是以一个大小为O(n)的哈希表为代价的。

思路3:

还可以把当前序列当成是一个下标和下标对应值是相同的数组(时间复杂度为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、代码

Jack Cui
阿里云ECS

发表评论

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