C++(后台开发面试题)

今天进行了今日头条一轮的技术面试，面试官问了这样一道题，给定一个数组，长度为n，数组中的元素均为整数，范围是[0,n-1]，问如何判断数组中是否出现重复数字。
这道题不算难，如果对时间复杂度和空间复杂度没有要求的话，那就直接使用二重循环进行遍历，代码如下：时间复杂度为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;
}

当然这是最暴力的方法，为了将时间复杂度降到O(n)，想再定义一个大小为n的向量用于记录数组元素出现的次数进行判断，空间复杂度为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;
}

然后面试官就问能不能在时间复杂度不变的情况下使空间复杂度降低。
于是想到这个数组的元素是比较特殊的，假如不存在重复元素排序后的的数组会是连续的，也即第i个元素是数字i-1，但是如果使用常用的排序方法，时间复杂度至少为O(nlogn)，所以这里需要利用到数组的特殊性进行排序，即将数字i-1交换到数组中第i个位置。
代码实现如下：时间复杂度O(n)，空间复杂度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;
}

记录一下……