爱上编程网

[LC] 287. Find the Duplicate Number

  • 时间:2019-12-19 15:33 编辑:青柠小助手 来源:网络游戏 阅读:73685
  • 扫一扫,手机访问
摘要:[LC] 287. Find the Duplicate Number

标签:solution   mod   sum   sam   constant   must   int   fas   ast   

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.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

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.

Same Algorithm with LC. 142

Time: O(N)

class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int fast = nums[nums[0]];
        int slow = nums[0];
        while (fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        int head = 0;
        while (head != slow) {
            head = nums[head];
            slow = nums[slow];
        }
        return slow;
    }
}

[LC] 287. Find the Duplicate Number

标签:solution   mod   sum   sam   constant   must   int   fas   ast   

原文地址:https://www.cnblogs.com/xuanlu/p/12067018.html

  • 全部评论(0)
最新发布的资讯信息
【数码/游戏/手机|网络游戏】画一棵漂亮的樱花树(不同种樱花+玫瑰+圣诞树喔)(2019-12-19 15:35)
【数码/游戏/手机|网络游戏】conda pip 安装 dgl 并运行demo 出现:Segmentation fault (core dumped) 错误(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】docker image换包步骤(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】Cron表达式(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】DRF单表序列化和反序列化(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】[LC] 287. Find the Duplicate Number(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】正则表达式常用匹配(2019-12-19 15:33)
【数码/游戏/手机|网络游戏】redis(2019-12-19 15:32)
【数码/游戏/手机|网络游戏】并发测试->countDownLatch(2019-12-19 15:32)
【数码/游戏/手机|网络游戏】console 打印消息时,可以使用 %c 指定随后的文本样式; %s 可引用参数变量。(2019-12-19 15:32)
展开