題目描述

長度為n的數(shù)組nums里的所有數(shù)字都在0～n-1的范圍內(nèi)，數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次，請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)數(shù)字返回涵卵。例如：

輸入：[2,3,1,0,2,5,3]
輸出：2或3

解題思路

1.遍歷法

先定義一個(gè)集合set，從頭開始遍歷數(shù)組中的元素荒叼，每遍歷一個(gè)元素就將該元素插入到定義的集合中轿偎，由于集合中的元素不能有重復(fù)，因此當(dāng)插入集合失敗時(shí)被廓，這個(gè)插入失敗的元素就是我們要找的重復(fù)數(shù)字坏晦。C++代碼實(shí)現(xiàn)如下：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        // 定義一個(gè)集合s
        set<int> s;
        // 保存insert函數(shù)的返回值，集合插入失敗時(shí)p.second 為bool值false
        pair<set<int>::iterator, bool> p;
        // 遍歷數(shù)組中的元素
        for(int i=0; i<nums.size(); i++){
            p = s.insert(nums[i]);
            if(!p.second)
                return nums[i];
        }
        // 沒有重復(fù)元素時(shí)返回 -1 
        return -1;
    }
};

2.下標(biāo)定位法

n個(gè)數(shù)字都在0～n-1范圍內(nèi)，如果沒有重復(fù)的數(shù)字昆婿，并且數(shù)組是有序的球碉，排好序后數(shù)字m應(yīng)該剛好在下標(biāo)m的位置上。從頭到尾掃描數(shù)組仓蛆，當(dāng)掃描到下標(biāo)為i的數(shù)字時(shí)睁冬，首先比較這個(gè)數(shù)字m是否等于下標(biāo)i，如果等于就繼續(xù)掃描下一個(gè)數(shù)字看疙，如果不等于豆拨，就讓它和第m個(gè)數(shù)字進(jìn)行比較，如果它和第m個(gè)數(shù)字相等能庆，那么出現(xiàn)了重復(fù)直接返回這個(gè)數(shù)字施禾，如果不相等，則將它和第m個(gè)數(shù)字進(jìn)行交換搁胆，即把m放到第m個(gè)位置上弥搞。重復(fù)這個(gè)過程，直到出現(xiàn)一個(gè)重復(fù)的數(shù)字渠旁。C++代碼實(shí)現(xiàn)如下：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            //下標(biāo)為i的位置上的元素nums[i]不是i時(shí)和下標(biāo)為nums[i]位置的元素做比較
            while(nums[i] != i){  
                // 下標(biāo)為nums[i]位置的元素也為nums[i]時(shí)拓巧，出現(xiàn)重復(fù)數(shù)字
                if(nums[nums[i]] == nums[i])
                    return nums[i];
                else{  // 下標(biāo)為nums[i]位置的元素不為nums[i]時(shí)，將它和下標(biāo)為i位置的元素做交換
                    int temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
            }
        } //沒有重復(fù)數(shù)字時(shí)一死，返回-1 
        return -1;
    }
};