leetcode287-寻找重复数

原题

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

示例1:

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

示例2:

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

说明:

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

解法

思想

有排序和哈希集的方法,但要满足4点限制,可以使用二分查找或快慢指针:
1. 二分查找,参考 https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/
2. 快慢指针,将index看成有向图里的节点,将对应的value看成节点指向的节点。那么有重复元素必然会形成环。如图:

示例1:[1,3,4,2,2]

示例2:[3,1,3,4,2]

那么入环的节点值就是重复出现的元素,可以使用leetcode142-环形链表II的双指针法来找出入环的元素。

代码

哈希集:

class Solution {
    public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i:nums){
            if(set.contains(i)) return i;
            set.add(i);
        }
        return -1;
    }
}

二分查找:

public class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1;
        int right = len - 1;
        while (left < right) {
            // int mid = left + (right - left) / 2;
            int mid = (left + right) >>> 1;
            int counter = 0;
            for (int num : nums) {
                if (num <= mid) {
                    counter += 1;
                }
            }
            if (counter > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

快慢指针:

class Solution {
     public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do{
            slow = nums[slow]; //相当于走一步
            fast = nums[nums[fast]]; //相当于走两步
        } while (slow!=fast);
        slow = nums[0];
        while (slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode287-%e5%af%bb%e6%89%be%e9%87%8d%e5%a4%8d%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月7日
下一篇 2020年1月8日

相关推荐

  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明: 不要使用任何内置的库函数,如  sqrt。 示例1: …

    算法 2020年1月5日
    0150
  • 剑指offer13-机器人的运动范围

    原题(来源Leetcode) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下…

    算法 2020年4月8日
    0110
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0650
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode430-扁平化多级双向链表

    原题 您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如下面的示例所示…

    2019年12月17日
    0100
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    080
  • 程序员面试金典08.11-硬币

    原题(来源Leetcode) 硬币。给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007) 示…

    算法 2020年4月23日
    0170
  • leetcode392-判断子序列

    原题 https://leetcode.cn/problems/is-subsequence/description 解法 最简单的双指针略。 对于进阶场景:如果有大量输入的 S,…

    算法 2024年3月24日
    060

发表回复

登录后才能评论