题解 | #数组中重复的数字#

#include <fstream>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        for(int i=0;i<numbers.size();i++){
            if(numbers.size()==0){
                return -1;
            }
            while(numbers[i]!=i){
                if (numbers[i]==numbers[numbers[i]]) {
                   return numbers[i];     
                }            
                swap(numbers[i], numbers[numbers[i]]);
            }

    }
    return -1;
    }

};

按照顺序将数组中每个值都交换到与值对应下标的位置，交换swap的目的是保存目标位置的值，并且不另外占用存储空间，数组中的每个值仅需进行一次交换，故时间复杂度为O(n)，除了索引和swap之外没有额外占用栈空间，因此空间复杂度为O(1)。

此外，看到有一个解法是建立一个集合set，把数组中的值一个个丢进去，判断set中是否已经存在同样的值，这样做的时间复杂度其实是O(nlogn), 因为set的搜索的时间复杂度为O(logn)。