find_the_duplicate_number
1# @leet start 2class Solution: 3 def findDuplicate(self, nums: list[int]) -> int: 4 """ 5 The solution that meets this problem is floyd's tortoise and hare 6 algorithm. 7 We first start out by finding the cycle in nums by having a slow and fast 8 pointer, and breaking out when they intersect. 9 10 Next, we make both the tortoise and the hare travel at the same speed, 11 starting the tortoise from the start and the hare at the intersection. 12 Next, have both of them set to the value of their index, and return 13 either the tortoise or the hare when they're equal. 14 """ 15 slow = fast = nums[0] 16 17 while True: 18 slow = nums[slow] 19 fast = nums[nums[fast]] 20 if slow == fast: 21 break 22 23 fast = nums[0] 24 while slow != fast: 25 slow = nums[slow] 26 fast = nums[fast] 27 return fast 28 29 def cyclic_sort(self, nums: list[int]) -> int: 30 """ 31 This solution involves cyclically sorting the array. 32 At every iteration of the loop, we pick the first item of the array, 33 nums[0] and compare it to what is in its index, i.e. nums[nums[0]]. 34 35 We then swap these as long as they aren't the same, and continue. 36 37 This works, becuase we know that 0 isn't in the array. We also know 38 that only items with a duplicate will match the condition of 39 nums[0] == nums[nums[0]] because there needs to be at least two 40 of the same item in the array for this to be the case. 41 42 For an example, say [1, 2, 3, 3]. 43 We take 1, and check what's in its index, 2. 44 We see they are different, so we swap them: 45 [2, 1, 3, 3] 46 Next, we look at the index of 2, which is not 2, so we swap. 47 [3, 1, 2, 3] 48 Now, we check the 3rd index and find that it matches 3. 49 Thus, we've found the duplicate, and can return either 50 nums or nums[nums[0]]. 51 """ 52 while nums[0] != nums[nums[0]]: 53 nums[0], nums[nums[0]] = nums[nums[0]], nums[0] 54 55 return nums[0] 56 57 58# @leet end 59 60 61def test(): 62 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def findDuplicate(self, nums: list[int]) -> int: 5 """ 6 The solution that meets this problem is floyd's tortoise and hare 7 algorithm. 8 We first start out by finding the cycle in nums by having a slow and fast 9 pointer, and breaking out when they intersect. 10 11 Next, we make both the tortoise and the hare travel at the same speed, 12 starting the tortoise from the start and the hare at the intersection. 13 Next, have both of them set to the value of their index, and return 14 either the tortoise or the hare when they're equal. 15 """ 16 slow = fast = nums[0] 17 18 while True: 19 slow = nums[slow] 20 fast = nums[nums[fast]] 21 if slow == fast: 22 break 23 24 fast = nums[0] 25 while slow != fast: 26 slow = nums[slow] 27 fast = nums[fast] 28 return fast 29 30 def cyclic_sort(self, nums: list[int]) -> int: 31 """ 32 This solution involves cyclically sorting the array. 33 At every iteration of the loop, we pick the first item of the array, 34 nums[0] and compare it to what is in its index, i.e. nums[nums[0]]. 35 36 We then swap these as long as they aren't the same, and continue. 37 38 This works, becuase we know that 0 isn't in the array. We also know 39 that only items with a duplicate will match the condition of 40 nums[0] == nums[nums[0]] because there needs to be at least two 41 of the same item in the array for this to be the case. 42 43 For an example, say [1, 2, 3, 3]. 44 We take 1, and check what's in its index, 2. 45 We see they are different, so we swap them: 46 [2, 1, 3, 3] 47 Next, we look at the index of 2, which is not 2, so we swap. 48 [3, 1, 2, 3] 49 Now, we check the 3rd index and find that it matches 3. 50 Thus, we've found the duplicate, and can return either 51 nums or nums[nums[0]]. 52 """ 53 while nums[0] != nums[nums[0]]: 54 nums[0], nums[nums[0]] = nums[nums[0]], nums[0] 55 56 return nums[0]
def
findDuplicate(self, nums: list[int]) -> int:
4 def findDuplicate(self, nums: list[int]) -> int: 5 """ 6 The solution that meets this problem is floyd's tortoise and hare 7 algorithm. 8 We first start out by finding the cycle in nums by having a slow and fast 9 pointer, and breaking out when they intersect. 10 11 Next, we make both the tortoise and the hare travel at the same speed, 12 starting the tortoise from the start and the hare at the intersection. 13 Next, have both of them set to the value of their index, and return 14 either the tortoise or the hare when they're equal. 15 """ 16 slow = fast = nums[0] 17 18 while True: 19 slow = nums[slow] 20 fast = nums[nums[fast]] 21 if slow == fast: 22 break 23 24 fast = nums[0] 25 while slow != fast: 26 slow = nums[slow] 27 fast = nums[fast] 28 return fast
The solution that meets this problem is floyd's tortoise and hare algorithm. We first start out by finding the cycle in nums by having a slow and fast pointer, and breaking out when they intersect.
Next, we make both the tortoise and the hare travel at the same speed, starting the tortoise from the start and the hare at the intersection. Next, have both of them set to the value of their index, and return either the tortoise or the hare when they're equal.
def
cyclic_sort(self, nums: list[int]) -> int:
30 def cyclic_sort(self, nums: list[int]) -> int: 31 """ 32 This solution involves cyclically sorting the array. 33 At every iteration of the loop, we pick the first item of the array, 34 nums[0] and compare it to what is in its index, i.e. nums[nums[0]]. 35 36 We then swap these as long as they aren't the same, and continue. 37 38 This works, becuase we know that 0 isn't in the array. We also know 39 that only items with a duplicate will match the condition of 40 nums[0] == nums[nums[0]] because there needs to be at least two 41 of the same item in the array for this to be the case. 42 43 For an example, say [1, 2, 3, 3]. 44 We take 1, and check what's in its index, 2. 45 We see they are different, so we swap them: 46 [2, 1, 3, 3] 47 Next, we look at the index of 2, which is not 2, so we swap. 48 [3, 1, 2, 3] 49 Now, we check the 3rd index and find that it matches 3. 50 Thus, we've found the duplicate, and can return either 51 nums or nums[nums[0]]. 52 """ 53 while nums[0] != nums[nums[0]]: 54 nums[0], nums[nums[0]] = nums[nums[0]], nums[0] 55 56 return nums[0]
This solution involves cyclically sorting the array. At every iteration of the loop, we pick the first item of the array, nums[0] and compare it to what is in its index, i.e. nums[nums[0]].
We then swap these as long as they aren't the same, and continue.
This works, becuase we know that 0 isn't in the array. We also know that only items with a duplicate will match the condition of nums[0] == nums[nums[0]] because there needs to be at least two of the same item in the array for this to be the case.
For an example, say [1, 2, 3, 3]. We take 1, and check what's in its index, 2. We see they are different, so we swap them: [2, 1, 3, 3] Next, we look at the index of 2, which is not 2, so we swap. [3, 1, 2, 3] Now, we check the 3rd index and find that it matches 3. Thus, we've found the duplicate, and can return either nums or nums[nums[0]].
def
test():