aboutsummaryrefslogtreecommitdiff
path: root/single_number2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'single_number2.cpp')
-rw-r--r--single_number2.cpp29
1 files changed, 29 insertions, 0 deletions
diff --git a/single_number2.cpp b/single_number2.cpp
new file mode 100644
index 0000000..907fee0
--- /dev/null
+++ b/single_number2.cpp
@@ -0,0 +1,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
+}