aboutsummaryrefslogtreecommitdiff
path: root/single_number2.cpp
blob: 907fee0f1387e267b60ba9af606b271077f30419 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 137. Single Number II
#include "leetcode.h"

/*
 * given an integer array 'nums' where every element appears three times except
 * for one, which appears exactly once. find the single element and return it.
 * you must implement a solution with a linear runtime complexity and use only
 * constant extra space.
 */

class Solution {
public:
  int singleNumber(vector<int> &nums) {
    unordered_map<int, int> um;
    for (auto i : nums)
      um[i]++;
    for (auto i : um)
      if (i.second == 1)
        return i.first;
    return -1;
  }
};

int main() {
  Solution obj;
  vector<int> n1 = {2, 2, 3, 2}, n2 = {0, 1, 0, 1, 0, 1, 99};
  printf("%d\n", obj.singleNumber(n1)); // expect: 3
  printf("%d\n", obj.singleNumber(n2)); // expect: 99
}