C ++中的无序映射

Question

我正在尝试使用 unordered map:

在 C++ 中实现这个问题

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 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' 没有可行的重载运算符 []
        如果（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'（又名 'const int'）的已知转换
      运算符[]（常量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'（又名 '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"）。

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

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

但是，正如评论中所述，您不需要任何额外的容器来解决这个难题。约束 "Could you implement it without using extra memory?" 实际上是对解决方案的提示。在非空整数数组中有一个数学属性，其中每个元素出现两次 (!) 除了一个。

此外，我建议使用变量名 i 作为索引并调用迭代器 it，但这只是个人喜好。

Answer 2

您不需要 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 操作也具有交换性属性：

A xor B xor A == A xor A xor B == 0 xor B == B

我想你现在可以在没有额外内存的情况下理解实现的想法了。

C ++中的无序映射

Unordered map in c++

c++

unordered-map

c++11