admin 管理员组文章数量: 1087818
[勇者闯LeetCode] 169. Majority Element
[勇者闯LeetCode] 169. Majority Element
Description
Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋
times.You may assume that the array is non-empty and the majority element always exist in the array.
Information
- Tags: Array | Divide and Conquer | Bit Manipulation
- Difficulty: Easy
Solution
利用位操作,先初始化输出元素为首元素,其出现次数cnt
为1,扫描数组,若当前元素与输出元素相同,则cnt
加1;否则cnt
减1,且cnt
为0时,将输出元素重置为当前元素,出现次数cnt
重置为1,扫描结束后输出元素将是数组中出现次数超过一半的那个元素。
C++ Code
class Solution {
public:int majorityElement(vector<int>& nums) {int ans = nums[0], cnt = 1;for (const auto& num : nums) {if (num == ans) {++cnt;}else {--cnt;if (cnt == 0) {ans = num;cnt = 1;}}}return ans;}
};
本文标签: 勇者闯LeetCode 169 Majority Element
版权声明:本文标题:[勇者闯LeetCode] 169. Majority Element 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.roclinux.cn/b/1694386587a251465.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论