Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once

非常好的题目,开始是用二分做的,比如取数组为{1,2,3,3,4,5},mid应该是(5+1)/2 = 3,那么,如果小于等于mid的数的个数如果超过了3,那么重复的数字一定出现在[l,mid]之间,否则出现在[mid + 1,r]之间。以该数组为例,中位数为3,小于等于3的数一共有4个,大于3的数有两个,所以重复的数字在[1,3]之间。

发现效率挺感人的,看了一下discuss,恍然大悟,这题和142本质是一样的!

http://blog.csdn.net/accepthjp/article/details/53213998

这里说一下怎么转化成链表找环,把数组中的每一个下标和对应的数看成有向图中一个点到另一个点的边。

如果有一个数重复出现,那么一定有多个点指向它,因为它自己又必须指向一个数,那么这里面一定存在一个以他为起点的环,接下来只要找到这个换就行了。

一旦转化成142,后面应该就知道怎么做了,详细推导见上面的142题链接。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() > 1)
    	{
    		int slow = nums[0];
    		int fast = nums[nums[0]];
    		while (slow != fast)
    		{
    			slow = nums[slow];
    			fast = nums[nums[fast]];
    		}
    
    		fast = 0;
    		while (fast != slow)
    		{
    			fast = nums[fast];
    			slow = nums[slow];
    		}
    		return slow;
    	}
    	return -1;
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

54740
来自专栏Python小屋

哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

78980
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

13620
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

37980
来自专栏dalaoyang

递归基础思想

18930
来自专栏小二的折腾日记

牛客网刷题总结-剑指offer(1)

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行...

11510
来自专栏chenjx85的技术专栏

leetcode-39-组合总和(有趣的递归)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

13820
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

30140
来自专栏Python专栏

浅尝Python快速排序

15540
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

18960

扫码关注云+社区

领取腾讯云代金券