剑指offer50数组中重复的数字

剑指offer50

1、哈希
个人做题参考
时间复杂度O(n)， 空间复杂度O(n)

int duplicate(vector<int>& numbers) {
        unordered_map<int,int>mp;
        for(int x:numbers)
        {
            if(mp[x]==1)
                return x;
            else
                ++mp[x];
        }
        return -1;
    }

2、找正确位置法
分析：数组长度n,元素范围0-n-1;若元素放到对应其数值索引下标，放入时若已有合适元素，则找到重复元素，如3放入 nums3,若nums3已有元素，则找到重复。每个萝卜只需要找一次自己的坑，最多找n次
个人做题参考
时间复杂度：O(n) 空间复杂度:O(1)

int duplicate(vector<int>& numbers) {
        for(int i=0;i<numbers.size();i++)
        {
            if(numbers[i]!=i)
            {
                int temp=numbers[numbers[i]];
                if(numbers[i]==temp)//重复，提前剪枝
                    return numbers[i];
                numbers[numbers[i]]=numbers[i];
                numbers[i]=temp;
                --i; //不符合的交换，交换之后i位又要重新检查-1
            }
        }
        return -1;
    }

上述优化：不做不必要的交换，直接每个元素奔着自己的正确位置去(直接xunh避免递归，费空间)
个人做题参考

   int duplicate(vector<int>& numbers) {
        for(int i=0;i<numbers.size();i++)
        {
            if(numbers[i]!=i)
            {
                int val=numbers[i]; //当前值
                numbers[i]=-1;//第一个开始的位置空出
                while(numbers[val]!=-1&&val!=numbers[val]) //寻找当前值正确位置，并放入
                {
                    int temp=numbers[val];
                    numbers[val]=val; //值放入正确位置
                    val=temp; //原来位置的值变成新的当前值，
                }
                if(numbers[val]!=-1)
                    return val;     
            }
        }
        return -1;
    }