给定一些整数, 请找出它们中的的”多数”. 一个数字如果超过了一半, 那么它就是多数. 假定这样的数是存在的.
比如, 给定 [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)
loading...
上一篇: 《Steem 指南》之 justyy 在线工具与 API 系列 - Discord 机器人
下一篇: 《Steem 指南》之 justyy 在线工具与 API 系列 - 见证人相互投票 - 谁没有给你投票?