JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

How can we prove that at least one duplicate number must exist in nums? Can you solve the problem without modifying the array nums? Can you solve the problem using only constant, O(1) extra space? Can you solve the problem with runtime complexity less than O(n2)?

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

Code

如果没有重复，将会出现 index 和数字一一对应的关系，如果有重复就会出现循环

推导方法请参考: 贾考博 LeetCode 142. Linked List Cycle II 兜兜转转还是一个圈

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        
        // 找到在环上的某一点相遇
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }
        
        // 找到进入环的点
        fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) {
                break;
            }
        }
        
        return slow;
    }
}

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[nums[0]]

        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        fast = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

func findDuplicate(nums []int) int {
    slow := 0
    fast := 0
    
    for {
        slow = nums[slow] 
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }
    
    fast = 0
    for {
        slow = nums[slow]
        fast = nums[fast]
        if slow == fast {
            break
        }
    }
    
    return slow
}