剑指Offer（五十）：数组中重复的数字

2018年1月21日10:28:30 9 7,934 °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++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        // 非法输入
        if(numbers == NULL || length <= 0){
            return false;
        }
        // 非法输入
        for(int i = 0; i < length; i++){
            if(numbers[i] < 0 || numbers[i] > length - 1){
                return false;
            }
        }
        // 遍历查找第一个重复的数
        for(int i = 0; i < length; i++){
            while(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]]){
                    *duplication = numbers[i];
                    return true;
                }
                swap(numbers[i], numbers[numbers[i]]);
            }
        }
        return false;
    }
};

Python：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        n = len(numbers)
        if n == 0:
            return False
        for i in range(n):
            if numbers[i] < 0 or numbers[i] > n-1:
                return False
        for i in range(n):
            while numbers[i] != i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]
        return False

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        n = len(numbers)
        if n == 0:
            return False
        for i in range(n):
            index = numbers[i]
            if index >= n:
                index -= n
            if numbers[index] >= n:
                duplication[0] = index
                return True
            numbers[index] += n
        return False

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

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

目前评论：9   其中：访客  5   博主  4

    • avatar easy 来自天朝的朋友 谷歌浏览器 Windows 10 中国 移动 1
      回复 2018年11月14日 下午5:01  沙发

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

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)
          回复 2018年11月14日 下午5:07  1层

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

        • avatar easy 来自天朝的朋友 谷歌浏览器 Windows 10 河北省 移动 1
          回复 2018年11月18日 下午10:12  板凳

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

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)
              回复 2018年11月19日 上午8:46  1层

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

            • avatar yuwua Germany 谷歌浏览器 Windows 10 德国 亚琛工业大学 1
              回复 2019年8月10日 上午3:10  地板

              博主您好，我发现一个小反例，假设一个长度为6的数组numbers为{0，5，5，5，1，2} ，是符合题目要求的，但是按照这里的思路求解的话：
              第一步 numbers[0]=0，遍历下一个元素；
              第二步 numbers[1]=5, numbers[5]=2, 因此交换位置，数组变为{0，2，5，5，1，5}
              第三步 numbers[1]=2, numbers[2]=5, 因此交换位置，数组变为{0，5，2，5，1，5}
              第三步 numbers[1]=5, numbers[5]=5, 因此交换位置，数组仍是{0，5，2，5，1，5}
              ……陷入死循环
              请问我是不是忽略了什么呢，感觉这个思路还不够全面？

                • avatar yuwua Germany 谷歌浏览器 Windows 10 德国 亚琛工业大学 1
                  回复 2019年8月10日 上午5:53  1层

                  @yuwua 不好意思，我蠢了，请忽略我的评论。

                    • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                      回复 2019年8月12日 上午9:32  2层

                      @yuwua :wink: :wink: 加油~

                  • avatar yyx 来自天朝的朋友 火狐浏览器 Ubuntu Linux 浙江省宁波市 电信 2
                    回复 2019年8月27日 下午9:06  4楼

                    博主大大，是不是只有python才能这么赋值呀numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]

                      • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                        回复 2019年8月27日 下午9:11  1层

                        @yyx 不仅python。现在，感觉这么写不太好，尽量还是分开吧。