数组中重复的数字

最新推荐文章于 2022-04-30 23:09:02 发布

源代码大师

最新推荐文章于 2022-04-30 23:09:02 发布

阅读量272

点赞数

分类专栏： C和C++算法完整教程 C和C++Everything教程

不予转载，严禁转载，违者必纠。

本文链接：https://blog.csdn.net/it_xiangqiang/article/details/113536244

版权

C和C++Everything教程同时被 2 个专栏收录

10029 篇文章 ¥99.90 ¥299.90

订阅专栏

超级会员免费看

C和C++算法完整教程

811 篇文章 ¥29.90 ¥99.00

订阅专栏

超级会员免费看

这篇博客探讨了如何在一个长度为n的数组中找到重复的数字，数组元素范围在0到n-1之间。博主提出了一种时间复杂度为O(n)，空间复杂度为O(1)的解决方案：通过比较每个位置的数字与其值是否相等，若不等则交换，直到找到重复的数字。给出的示例中，输入数组{2,3,1,0,2,5,3}，重复数字是2。" 112141298,10537308,5G NSA接入信令与空口流程解析,"['5G信令流程详解', '5G接入', 'NR', '网络架构']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

如题所示：

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2

思路

时间:O(n)，空间:O(1)）：如果位置i的数字m不等于i，与位置m的数字比较
–如果位置m的数字不等于m，那么交换，直到位置i的数字等于i或位置m的数字等于m
如果位置m的数字等于m，说明数字m存在重复

源代码如下：

 class Solution {
   
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output