随笔系列-寻找重复数（快慢指针、二分查找）

阅读量：

寻找数组中的重复整数

示例 1:

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

输入: [3,1,3,4,2]
输出: 3
说明：

原数组不得被修改（假设该数组为只读状态）。
额外空间的使用量需控制在 O(1) 的范围之内。
所采用算法的时间复杂度应低于 O(n²) 。
数组中仅包含一个重复出现的数字，但该数字可能出现多次。

方法一：快慢指针

链表判环法检测数组重复元素

复制代码

    class Solution {
    public int findDuplicate(int[] nums) {
        int fast=0;
        int slow=0;
        while(true){
            slow=nums[slow];
            fast=nums[nums[fast]];
            if(fast==slow){
                slow=0;
                break;
            }
        }
        while(true){
            fast=nums[fast];
            slow=nums[slow];

全部评论 (0)

还没有任何评论哟~