186-找出数组中的重复数字 布满荆棘的人生 2022-10-29 12:27 190阅读 0赞 **题目如下:** 给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 **说明:** 不能更改原数组(假设数组是只读的)。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字,但它可能不止重复出现一次。 **下面使用环链表入口节点的方法求解:** #include<stdio.h> int findDuplicate(int *nums) { int fast = 0; int slow = 0; do { slow = nums[slow]; fast = nums[nums[fast]]; }while (fast != slow); slow = 0; while (fast != slow) { fast = nums[fast]; slow = nums[slow]; } return slow; } int main() { int arr[]={ 1,2,3,3,4}; printf("%d\n",findDuplicate(arr)); return 0; } **运行截图如下:** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/9f478c692fcc4c15b1579938b5ee3687.png
还没有评论,来说两句吧...