0

我认为这很简单,但是当我将这个向量传递给它时它返回了 true:

   int arr2[] =  {1, 6, 7, 89, 69, 23, 19, 100, 8, 2, 50, 3, 11, 90};               
   std::vector<int> vec2(arr2, arr2 + sizeof(arr2)/sizeof(int));

算法很简单:

(1) 实例化地图。(2) 对于向量中的每个 int,(2i) 如果它不在 map 中,则添加它,(2ii) 如果它在 map 中,则返回 true。(3) 如果到达 for 循环的末尾,则返回 false。

bool contains_repeats_1(const std::vector<int>& V) { 
    std::map<int,bool> M;
    for (std::vector<int>::const_iterator it = V.begin(); it != V.end(); it++) {
        if (M.count(*it) != 0) { 
             M.insert(std::pair<int,bool>(*it, true));
        } else {
            return true;
        }
    }
    return false; 
} 

另外,我将不胜感激有关如何更好地解决此问题的任何建议。我正在使用 Apple XCode,它没有包含 unordered_map 的库。

4

2 回答 2

3

更轻松:

std::set<int> s(vec2.begin(), vec2.end());
return s.size() < vec2.size();

std::set这依赖于 an不包含重复项这一事实。因此,如果向量中有任何重复项,则集合会更小。

如果您担心这会执行太多不必要的副本,您可以使用循环并在第一个副本处中断:

std::set<int> s;
for (int i : vec2) {
  if (!s.insert(i).second) return true;
}
return false;
于 2013-11-07T16:20:34.083 回答
1
std::sort(V.begin(), V.end());
if (std::adjacent_find(V.begin(), V.end()) != V.end()) {
    // found a duplicate
}
于 2013-11-07T16:30:36.823 回答