今天進(jìn)行了今日頭條一輪的技術(shù)面試，面試官問了這樣一道題，給定一個(gè)數(shù)組，長度為n，數(shù)組中的元素均為整數(shù)，范圍是[0,n-1]，問如何判斷數(shù)組中是否出現(xiàn)重復(fù)數(shù)字。
這道題不算難，如果對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度沒有要求的話，那就直接使用二重循環(huán)進(jìn)行遍歷，代碼如下：時(shí)間復(fù)雜度為O(n^2)

bool repeat(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = i + 1; j < v.size(); j++) {
            if (v[j] == v[i]) return true;
        }
    }
    return false;
}

當(dāng)然這是最暴力的方法，為了將時(shí)間復(fù)雜度降到O(n)，想再定義一個(gè)大小為n的向量用于記錄數(shù)組元素出現(xiàn)的次數(shù)進(jìn)行判斷，空間復(fù)雜度為O(n)

bool repeat(vector<int> &v) {
    vector<int> count(v.size(), 0);
    for (int i = 0; i < v.size(); i++) {
        if (count[v[i]] == 1) return true;
        count[v[i]] == 1;
    }
    return false;
}

然后面試官就問能不能在時(shí)間復(fù)雜度不變的情況下使空間復(fù)雜度降低。
于是想到這個(gè)數(shù)組的元素是比較特殊的，假如不存在重復(fù)元素排序后的的數(shù)組會(huì)是連續(xù)的，也即第i個(gè)元素是數(shù)字i-1，但是如果使用常用的排序方法，時(shí)間復(fù)雜度至少為O(nlogn)，所以這里需要利用到數(shù)組的特殊性進(jìn)行排序，即將數(shù)字i-1交換到數(shù)組中第i個(gè)位置。
代碼實(shí)現(xiàn)如下：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

bool repeat(vector<int> &v) {
    for (int i = 0; i < v.size(); i++) {
        while (v[i] != i){
            int temp = v[i];
            if (v[i] == v[temp]) return true;
            else {
                int t = v[i];
                v[i] = v[temp];
                v[temp] = t;
            }
        }
    }
    return false;
}

記錄一下……