网站开发语音网站推广站点建设与策划

网站开发语音,网站推广站点建设与策划,手机网站设计公司立找亿企邦,seo教程合集给定一个包含 n 1 个整数的数组 nums #xff0c;其数字都在 [1, n] 范围内#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 #xff0c;返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量…给定一个包含n 1个整数的数组nums其数字都在[1, n]范围内包括1和n可知至少存在一个重复的整数。假设nums只有一个重复的整数返回这个重复的数。你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。示例 1输入nums [1,3,4,2,2]输出2示例 2输入nums [3,1,3,4,2]输出3示例 3 :输入nums [3,3,3,3,3]输出3提示1 n nums.length n 11 nums[i] nnums中只有一个整数出现两次或多次其余整数均只出现一次算法解析构建链表逻辑把数组的索引看作链表节点元素值看作下一个节点的索引因数组元素范围是[1,n]不会越界。由于存在重复数链表会形成环重复数就是环的入口节点。快慢指针找环慢指针slow每次走 1 步快指针fast每次走 2 步最终会在环内某点相遇。找环的入口从数组起点nums[0]和环内相遇点同时出发两个指针每次走 1 步相遇处即为环的入口也就是重复的数。示例验证以nums [1,3,4,2,2]为例链表结构0 → 1 → 3 → 2 → 4 → 2环的入口是2。快慢指针相遇后起点指针与慢指针会在2处相遇返回结果2。Python代码from typing import List class Solution: 寻找数组中重复的数字满足条件数组长度n1元素范围[1,n]仅一个重复数可能重复多次 核心算法快慢指针弗洛伊德环检测时间复杂度O(n)空间复杂度O(1)不修改原数组 def findDuplicate(self, nums: List[int]) - int: 查找数组中重复的数字 :param nums: 输入数组长度为n1元素范围[1,n]保证有且仅有一个数字重复 :return: 重复的数字 # 边界校验数组长度小于2时无意义题目保证输入合法此处为鲁棒性补充 if len(nums) 2: raise ValueError(数组长度至少为2) # 1. 快慢指针找环内相遇点慢指针走1步快指针走2步 slow nums[0] fast nums[0] while True: slow nums[slow] # 慢指针每次走1步 fast nums[nums[fast]] # 快指针每次走2步 if slow fast: # 快慢指针相遇说明存在环退出循环 break # 2. 找环的入口重复数就是环的入口 # 原理从数组起点和相遇点同时出发每次走1步相遇处即为环入口 ptr nums[0] # 指针1从数组起点出发 while ptr ! slow: ptr nums[ptr] # 指针1走1步 slow nums[slow] # 指针2原慢指针走1步 return ptr # -------------------------- 测试用例 -------------------------- if __name__ __main__: solution Solution() # 测试用例1基础情况 nums1 [1, 3, 4, 2, 2] print(f测试用例1: {nums1} → 重复数{solution.findDuplicate(nums1)}) # 预期输出2 # 测试用例2重复数在开头 nums2 [2, 2, 2, 2, 2] print(f测试用例2: {nums2} → 重复数{solution.findDuplicate(nums2)}) # 预期输出2 # 测试用例3最小边界数组长度2 nums3 [1, 1] print(f测试用例3: {nums3} → 重复数{solution.findDuplicate(nums3)}) # 预期输出1 # 测试用例4重复数在中间 nums4 [3, 1, 3, 4, 2] print(f测试用例4: {nums4} → 重复数{solution.findDuplicate(nums4)}) # 预期输出3LeetCode提交代码class Solution: def findDuplicate(self, nums: List[int]) - int: # 1. 快慢指针找环内相遇点 slow nums[0] fast nums[0] while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break # 2. 找环的入口即重复数 ptr nums[0] while ptr ! slow: ptr nums[ptr] slow nums[slow] return ptr程序运行截图展示总结题目要求在长度为n1的数组中找到唯一重复的数字元素范围[1,n]要求不修改数组且使用O(1)空间。通过将数组视为链表索引为节点值为下一节点利用快慢指针检测环找环快指针每次2步与慢指针每次1步相遇找入口从起点和相遇点同步移动相遇点即为重复数。示例[1,3,4,2,2]中链表形成环2→4→2入口2即为解。算法时间复杂度O(n)空间O(1)。Python代码通过双指针实现已验证边界用例。