剑指offer（1）数组中重复的数字

描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复服务器托管网的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：

进阶：时间复杂度，空间复杂度

方法一：利用set集合
核心思想：
引入set集合，遍历数组元素，检查元素是否在集合中，不在则将元素插入到集合里面；否则表明当前元素在数组中重复，返回当前元素。

核心代码：

int duplicate(vector& numbers) {
    set s;
    for(int i=0;i0)
            return numbers[i];
        else
            s.insert(numbers[i]);
    }
    return -1;
}

复杂度分析：
代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于引入额外的集合空间，因此空间复杂度为O(N)，最坏的情况是数组中的元素都不重复。

时间复杂度O(N)
空间复杂度O(N)

方法二：数据重排
核心思想：
重头到尾扫描数组S中的每一个元素，当扫描到第i个元素的时候，比较第i个元素位置的值m是否等于i，如果相等，则说明该元素已经在排好序的服务器托管网位置，继续扫描其他元素；如果不相等，先判断m是否等于S[m]，相等则说明不同位置上的元素值相等，即元素重复。直接返回元素；否则交换m和S[m]将他们放置到排好序的位置

int duplicate(vector& numbers) {
    int i=0,n=numbers.size();
    while(i

复杂度分析：

代码使用了循环，循环次数为数组大小，因此该方法的时间复杂度为O(N)。由于没有采用额外的数组空间，空间复杂度为O(1)

时间复杂度O(N)

空间复杂度O(1)

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 构建 JavaScript ChatGPT 插件

聊天插件系统是一种令人兴奋的新方式，可以扩展ChatGPT的功能，纳入您自己的业务数据，并为客户与您的业务互动增加另一个渠道。在这篇文章中，我将解释什么是聊天插件，它们能做什么，以及你如何用JavaScript建立你自己的聊天插件。 这篇文章（或OpenAI所…