Неупорядоченная карта в c ++

Question

Я пытаюсь реализовать эту проблему в C ++, используя unordered map:

Учитывая непустой массив целых чисел, каждый элемент появляется дважды, кроме одного. Найдите этот единственный.

Примечание:

Ваш алгоритм должен иметь линейную сложность во время выполнения. Не могли бы вы реализовать это без использования дополнительной памяти?

Пример 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;
      }
    } 
  }
};

Но, к сожалению, это не так Работа. Я получаю эту ошибку при компиляции

Line 16: Char 17: fatal error: no viable overloaded operator[] for type 'std::unordered_map'
        if (umap[*i] == 1) {
            ~~~~^~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:973:7: note: 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)
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/unordered_map.h:977:7: note: candidate function not viable: no known conversion from 'std::pair' to 'std::unordered_map, std::equal_to, std::allocator > >::key_type' (aka 'int') for 1st argument
      operator[](key_type&& __k)
      ^
1 error generated.

Я не могу понять ошибку. Кто-нибудь может мне объяснить?

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, содержащую ссылку на данные ключа и к данным стоимости. Вы можете легко получить данные о значении просто из итератора, не вызывая оператор индекса:

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

---

Однако, как указано в комментариях, вам не нужен дополнительный контейнер для решения этой головоломки. Ограничение "Не могли бы вы реализовать это без использования дополнительной памяти?" на самом деле намек на решение. Существует математическое свойство в непустом массиве целых чисел, где каждый элемент появляется дважды (!), За исключением одного.

---

Кроме того, я Рекомендую использовать имя переменной 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 );
}

Итак, logi c - вы пытаетесь вставить число, но если оно уже было, вы убери это. Другое преимущество этого подхода, помимо меньшего объема памяти, заключается в том, что после l oop у вас будет только один элемент в наборе - тот, который вам нужен. Так что вам не нужно повторять и искать.

Но правильное решение - это хитрость, о которой вы должны знать. Он основан на свойствах операции 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

Я думаю, что теперь вы можете получить представление о реализация без дополнительной памяти.