剑指offer——数组：数组中重复的数字

1、暴力

拿每个元素和后面所有的元素都比较一遍，如果有重复的，则返回；没有，就比较数组后面下一个的元素

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        int len=numbers.size();
        if(len==0||len==1)
            return -1;
        for(int i=0;i<len;i++)
        {
            //nums[i]是标准值，用来和后面数组内的其他所有元素比较的值
            for(int j=i+1;j<len;j++)
            {
                //nums[j]是被比较的值
                if(numbers[i]==numbers[j])
                {
                    return numbers[i];
                }
            }
        }
        return 0;
    }
};

2、位置重排

是吧数组内每个元素放在以当前元素为下标的数组位置上，如果当前元素不等于下标值（需要调整当前元素的位置，把它放在合适的位置上），并且调整前，应去的地方没有元素，说明此时要挪去的元素暂时还没有与它相同的，因此将当前元素放在该在的地方。

但此时将当前元素放入该放的地方之后，原来遍历的部分还需要再次比较（当把numbers[0]位置上的元素换出去之后，numbers[0]的位置上的元素是新换过来的，还需要再次比较被换过来的元素是否是应该此时numbers[0]位置上的数字），因此先将用于遍历的i减一，然后在下一次for循环后，i就会+1，因此下一次for循环处理的还是当前numbers[0]的位置

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        int len=numbers.size();
        if(len==0||len==-1)
            return -1;
        for(int i=0;i<len;i++)
        {
            //如果当前元素的值等于下标值
            if(numbers[i]==i)
            {
                //则证明当前元素不需要改变位置
                continue;
            }
            //如果当前元素位置不等于下标值，应该将当前元素换到以它为下标的地方
            else 
            {
                //如果当前元素应该在的地方已经有元素了，说明这个元素已经存在了，则返回当前元素
                if(numbers[i]==numbers[numbers[i]])
                {
                    return numbers[i];
                }
                //暂时还没有和当前元素相等的元素，则先将当前元素放在正确的地方
                else 
                {
                    swap(numbers[i],numbers[numbers[i]]);
                    //要把i先-1，循环1次后在+1，这样下一次for循环后还是比较数组原来位置上的数字
                    i--;
                }
            }
        }
        return -1;
    }
};

3、哈希表

建立一个哈希表，遍历数组，如果数组中的元素没出现过，证明未重复，则存入哈希表，如果出现过，证明重复了

哈希表的使用，以数组内的元素为键，设bool值为值

向map中存入数值为：map[numbers[i]]=true;

哈希表的查找：map.find()——find(键)——返回的值是一个迭代器，要用iter->first和 iter->second访问键值

如果没找到，返回end

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        int len=numbers.size();
        if(len==0||len==1)
            return -1;
        //新建哈希表
        unordered_map<int, bool> mp;
        //遍历数组
        for(int i=0;i<len;i++)
        {
            //如果没有出现，存入哈希表
            if(mp.find(numbers[i])==mp.end())
                //mp[numbers[i]]表示访问以numbers[i]为键对应的值
                mp[numbers[i]]=true;
            //出现，证明重复
            else
                return numbers[i];
        }
        return -1;
    }
};