implement majority in js

iostalks · iostalks · commit 0793fc3bc572 · 2019-01-08T08:23:33.000+08:00
diff --git a/Array/03.MajorityElement/MajorityElement.js b/Array/03.MajorityElement/MajorityElement.js
@@ -0,0 +1,20 @@
+// O(n) time, O(n) space
+var majorityElement = function(nums) {
+    // O(n) 空间复杂度的解法
+    const map = {}; // 存储元素出现的次数
+    nums.forEach(ele => {
+        if (!map[ele]) {
+            map[ele] = 1;
+        } else {
+            map[ele] = map[ele] + 1;
+        }
+    });
+    for (let key in map) {
+        if (map[key] > nums.length / 2) { // 查找出现次数大于一半的元素
+            return key;
+        }
+    }
+    return null;
+};
+
+// O(n) time, O(1) space
diff --git a/Array/03.MajorityElement/README.md b/Array/03.MajorityElement/README.md
@@ -22,7 +22,13 @@
 输出: 2
 ```
 
+## 思路
+1. O(n) time and O(n) space
+
+2. O(n) time and O(1) space
+使用 major 变量记录众数，count 记录遇到 major +1，非 major -1，最终 count 会大于0，major 即代表众数。
+
 ## 代码实现
 | C | C++ | Java | Python | JavaScript | PHP |
 | :--: | :--: | :--: | :--: | :---: | :---: |
-| 🤔 | 🤔 | 🤔 | 🤔 | 🤔 | 🤔 |
+| 🤔 | 🤔 | 🤔 | 🤔 | [😀](./MajorityElement) | 🤔 |
