数组重复元素查找：给定C++解法存在哪些问题？

问题需求 #

给定大小为N的数组a[]，元素取值范围为0到N-1，要求找出所有出现次数超过一次的元素。若数组中0到N-1每个元素恰好出现一次（无重复），则输出-1。

输入示例：

N = 4
a[] = {0,3,1,2}

输出：-1
解释：0到3的所有元素均存在于数组中，无重复元素，故输出-1。

待分析的C++代码 #

vector<int> duplicates(int arr[], int n) {
        unordered_set<int> m;
        vector<int> ans;
        for(int i=0;i<n;i++){
            //if element is found
            if(m.find(arr[i])!=m.end())
                ans.push_back(arr[i]);
            //if element is not found
            else
                m.insert(arr[i]);
    }
    if(ans.empty())
        ans.push_back(-1);
    return ans;
}

代码存在的问题 #

• 重复元素会被多次加入结果集：比如当数组为{0,0,0}时，代码会在每次遇到重复的0时都将其加入ans，最终结果是[0,0]，但题目只需要记录出现过重复的元素，正确结果应该是[0]。
• 结果未按顺序排列：多数编程题会要求输出的重复元素按升序排列，比如输入数组{3,3,1,1}，当前代码输出[3,1]，不符合常规的有序输出要求。
• 空间复杂度可优化：由于元素取值范围固定为0到N-1，完全可以用原地标记（如将对应索引的元素取负）或固定大小的数组来检测重复，空间复杂度能从O(N)降到O(1)（结果数组除外），而当前使用unordered_set的方案不是最优解。

内容的提问来源于stack exchange，提问作者Ishita