给定一些整数, 请找出它们中的的”多数”. 一个数字如果超过了一半, 那么它就是多数. 假定这样的数是存在的.
比如, 给定 [1, 1, 1, 1, 2, 2, 2], 您的算法将给出 答案 1 因为1出现了4次超过了一半(3.5次)
最直接的算法就是通过 字典(或者HASHMAP)记录每个出现数字的次数, 然后只要判断其中一个出现超过一半了, 就返回它.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Solution { public: /* * @param nums: a list of integers * @return: find a majority number */ int majorityNumber(vector<int> &nums) { unordered_map<int, int> counter; int half = nums.size() / 2; for (auto n: nums) { if (counter.count(n) == 0) { counter[n] = 0; } counter[n] ++; if (counter[n] >= half) { return n; } } return -1; // not found } }; |
class Solution { public: /* * @param nums: a list of integers * @return: find a majority number */ int majorityNumber(vector<int> &nums) { unordered_map<int, int> counter; int half = nums.size() / 2; for (auto n: nums) { if (counter.count(n) == 0) { counter[n] = 0; } counter[n] ++; if (counter[n] >= half) { return n; } } return -1; // not found } };
C++中的unordered_map插入复杂度是常数 O(1), 平均情况下查找也是O(1) – 注意最坏情况下是 O(n). 上面的算法 时间复杂度是 O(n) 但是空间复杂度是 O(n) – 因为用了 unordered_map
Boyer–Moore 多数投票算法
Boyer–Moore 多数投票算法 只需要常数O(1) 空间复杂度, 况且, 假定多数存在的话, 也只需要一遍循环 O(n) 即可.
其实原理就是: 我们只需要记录当前最多数的情况即可. 如果存在多数, 那么算法一定会找到它. 否则, 该算法返回顺序数字中的一个数. 往往我们需要第二次循环用于确认有一个多数.
拿输入 [1 1 1 2 2 3 1] 为例, m 记录着当前的最多数, c 是计数. 当 c 变成0的时候, 则下一轮就得更新m 为下一轮的数字.
当这一轮的数字和 m 是一样的, 我们就增加投票数 c 否则就把 c 减掉一.
[*1 1 1 2 2 3 1] m = 1, c = 1
[1 *1 1 2 2 3 1] m = 1, c = 2
[1 1 *1 2 2 3 1] m = 1, c = 3
[1 1 1 *2 2 3 1] m = 1, c = 2
[1 1 1 2 *2 3 1] m = 1, c = 1
[1 1 1 2 2 *3 1] m = 1, c = 0
[1 1 1 2 2 3 *1] m = 1, c = 1
第一次循环, 我们知道 m=1 超过了一半. 整个过程可以用以下 C++ 代码来演示.
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 | class Solution { public: /* * @param nums: a list of integers * @return: find a majority number */ int majorityNumber(vector<int> &nums) { int c = 0, m = nums[0]; for (int i = 0; i < nums.size(); ++ i) { if (c == 0) { m = nums[i]; c ++; } else if (m == nums[i]) { c ++; } else { c --; } } // check if there is a majority int counter = 0; for (int i : nums) { if (i == m) counter++; } if (counter < (nums.size() + 1) / 2) return -1; return m; } }; |
class Solution { public: /* * @param nums: a list of integers * @return: find a majority number */ int majorityNumber(vector<int> &nums) { int c = 0, m = nums[0]; for (int i = 0; i < nums.size(); ++ i) { if (c == 0) { m = nums[i]; c ++; } else if (m == nums[i]) { c ++; } else { c --; } } // check if there is a majority int counter = 0; for (int i : nums) { if (i == m) counter++; } if (counter < (nums.size() + 1) / 2) return -1; return m; } };
英文: Data Structures amp Algorithms Series – Majority Number (Boyer–Moore majority vote algorithm)
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK