C ++中的无序映射

Question

我正在尝试使用unordered map在C ++中实现此问题：

给出一个非空的整数数组，每个元素出现两次，除了一个。找到那一个。

注意：

您的算法应具有线性的运行时复杂度。您可以在不使用额外内存的情况下实现它吗？

示例1：

输入：[2,2,1]输出：1

示例2：

输入：[4,1,2,1,2]输出：4

我的解决方案：

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    std::unordered_map<int, int> umap;

    for (auto i = nums.begin(); i != nums.end(); i++) {
      umap[*i] = umap[*i] + 1;
    }

    for (auto i = umap.begin(); i != umap.end(); i++) {
      if (umap[*i] == 1) {
        return *i;
      }
    } 
  }
};

但是很遗憾，它不起作用。编译时出现此错误

第16行：字符17：致命错误：类型'std :: unordered_map'没有可行的重载operator []如果（umap [* i] == 1）{~~~~ ^ ~~/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:973:7：注意：候选函数不可行：对于第一个参数，没有从'std :: pair'到'const std :: unordered_map，std :: equal_to，std :: allocator>> :: key_type'（aka'const int'）的已知转换运算符[]（const key_type＆__k）^/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:977:7：注意：候选函数不可行：第一个参数没有从'std :: pair'到'std :: unordered_map，std :: equal_to，std :: allocator>> :: key_type'（aka'int'）的已知转换运算符[]（key_type && __k）^产生1个错误。

我无法理解该错误。谁能向我解释？

Answer 1

错误的相关部分是：

candidate function not viable: no known conversion from
   'std::pair' to
   'const std::unordered_map, std::equal_to, std::allocator > >::key_type'
       (aka 'const int')
for 1st argument operator[](const key_type& __k)

因此，这意味着在umap[*i] == 1中使用下标运算符时，*i的类型为std::pair，而运算符期望的类型为const int（请参阅“ aka”）。

这是因为映射迭代器将std::pair返回包含对键数据和的引用到值数据。您可以从迭代器中轻松获取值数据，而无需调用下标运算符：

std::pair

---

但是，如评论中所述，您不需要任何其他容器即可解决此难题。约束“您可以在不使用额外内存的情况下实现它吗？”实际上是解决方案的提示。在非空整数数组中有一个数学属性，其中每个元素都显示为[[twice（！），除了一个。

---

此外，我建议使用变量名

if (i->second == 1)
  return i->first;

作为索引并调用迭代器i，但这只是个人喜好。

Answer 2

您不需要it，因为在这种情况下，std::unordered_map就足够了：

std::unordered_set

因此，您尝试插入一个数字是逻辑，但是如果已经存在，则将其删除。除了较小的内存占用空间外，此方法的另一个好处是循环后，集合中将只有一个元素-需要一个元素。因此，您无需进行迭代和搜索。
但是正确的解决方案是您应该注意的一个技巧。它基于std::unordered_set<int> set;
for( auto i : nums ) {
   auto p = set.insert( i );
   if( !p.second ) set.erase( p.first );
}
操作的属性：
xor

并且因为A xor A == 0 for any A
A xor 0 == A for any A
操作也具有交换属性：
xor

我认为您现在无需额外的内存即可了解实现的想法。