专栏首页算法码上来每日算法系列【LeetCode 287】寻找重复数

每日算法系列【LeetCode 287】寻找重复数

题目描述

给定一个包含 个整数的数组 ,其数字都在 到 之间(包括 和 ),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

说明

  • 不能更改原数组(假设数组是只读的)。
  • 只能使用额外的 的空间。
  • 时间复杂度小于 。
  • 数组中只有一个重复的数字,但它可能不止重复出现一次。

示例1

输入:
[1,3,4,2,2]
输出:
2

示例2

输入:
[3,1,3,4,2]
输出:
3

题解

二分法

根据抽屉原理,如果大小为 的抽屉里放了大于 个数,那么一定有一个抽屉里至少放了两个数。

那我们不妨统计一下数组中有多少个数满足 ,数量记为 。

如果 ,那么根据抽屉原理, 到 中一定有一个数出现了至少两次。

反之如果 ,那么说明满足 的数的数量是 ,而抽屉大小是 ,所以根据抽屉原理, 到 中一定有一个数出现了至少两次。

综上,可以采用二分法,不断缩小 的范围,最终得到这个出现至少两次的数的值。

时间复杂度 。

快慢指针法

因为 中数据范围是 到 ,所以 。那么接着用 作为下标来索引值,得到 。如果 已经出现过了 ,那么重复值已经找到了。否则的话 还没出现过的话,继续用 作为下标来索引,直到出现重复值。

可以发现按照这种方法索引下去,形成了一个链,也就是 。最终这条链末端一定会产生出一个环,那么环的入口一定就是那个重复的数。

举个例子,如下图所示,最终环产生在了 上面,而 又是链进入环的入口,所以重复的数就是 。

那么如何求链表中的环呢?这其实是一道面试经常会问到的经典题,标准解法就是用两个快慢指针

初始时两个指针指着链表头结点,然后同时移动。慢指针一次移动一个结点,快指针一次移动两个结点。当下一次快指针又和慢指针相遇时,停止移动。然后用第三个指针指着头结点,慢指针留在原地,两者同时移动,都是一次移动一个结点,直到相遇。这时两者指着的结点就是环的入口了。

大家可以用上面的例子自己画图演示一下,我下面严格证明一下为什么这样是对的。

假设如下图所示,链表中链的长度是 ,环的长度是 。

假设慢指针和快指针第一次相遇时,慢指针移动的距离是 ,那么快指针移动距离就是 。

可以列出等式 ,也就是两者距离差值一定是环长度的正整数 倍,同时 是使得 的最小正整数,即 。这时候慢指针离入口的距离是 ,也就是说,慢指针只需要再多绕 个环的长度,就能恰好和从头结点而来的指针相遇在入口处。

时间复杂度 O(n) 。

扩展:

那有人可能会问了,那要是链最后回到了 ,不就没有链,只有环了吗?哪来的入口?这是对的,所以本题中限制了 数组里都是大于 的,如果范围是 到 的话,不能直接用数值但下标索引了,不然会出现下面这种情况,也就是 也在环里了。

其实这种情况我们只需要稍稍修改一下索引,让 不可能出现在环里就行了,也就是让 当作索引,如下图所示。最终重复的数只需要减去 就行了。

代码

二分法(c++)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;
        while (l < r) {
            int m = l+(r-l)/2;
            int cnt = 0;
            for (int i = 0; i < n+1; ++i) {
                if (nums[i] <= m) cnt++;
            }
            if (cnt > m) r = m;
            else l = m + 1;
        }
        return l;
    }
};

快慢指针法(c++)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        int find = 0;
        while (find != slow) {
            slow = nums[slow];
            find = nums[find];
        }
        return find;
    }
};

二分法(python)

class Solution:
    def findDuplicate(self, nums):
        n = len(nums) - 1
        l, r = 1, n
        while l < r:
            m = l+(r-l)//2
            cnt = sum([x<=m for x in nums])
            if cnt > m:
                r = m
            else:
                l = m + 1
        return l

快慢指针法(python)

class Solution:
    def findDuplicate(self, nums):
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        find = 0
        while find != slow:
            slow = nums[slow]
            find = nums[find]
        return find

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 105】打家劫舍第二弹:看好你的电瓶车!

    往期回顾:打家劫舍 I : 【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下![2]

    godweiyang
  • 【LeetCode 327】区间和的个数

    作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

    godweiyang
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • css显示全屏背景图片

    bye
  • 【位运算】只出现一次的数字 II,数电的知识终于用上了!

    https://leetcode-cn.com/problems/single-number-ii/

    机器视觉CV
  • 使用交互式地图和动画可视化伦敦的自行车流动性(上)

    近年来,自行车共享系统已经成为流行的出行方式,为大都市地区的市民提供了一种绿色、灵活的交通方式。世界上许多国家的政府都认为这是一种创新战略,可能会带来许多社会效...

    AiTechYun
  • LeetCode每日一题53: 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    benny
  • python multiprocessing 共享变量

    from multiprocessing import Process,Value import time import random

    用户5760343
  • Java面试系列17-编程题-读取服务器字符、实现序列化、计数器、1000阶乘、n出列问题等

    一,Java的通信编程,编程题(或问答),用JAVA SOCKET编程,读服务器几个字符,再写入本地显示? Server端程序: package test;...

    Java帮帮
  • .NET Fringe 定义未来

    在dotnetconf 2015会宣布了4.12-14 在波特兰召开 .NET Fringe http://dotnetfringe.org/ ,中文社区很少有...

    张善友

扫码关注云+社区

领取腾讯云代金券