C++实现LeetCode(169.求大多数)
作者:Grandyang 发布时间:2023-09-04 08:03:47
[LeetCode] 169. Majority Element 求大多数
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length
1 <= n <= 5 * 104
-231 <= nums[i] <= 231 - 1
Follow-up: Could you solve the problem in linear time and in O(1) space?
这是到求大多数的问题,有很多种解法,其中我感觉比较好的有两种,一种是用哈希表,这种方法需要 O(n) 的时间和空间,另一种是用一种叫摩尔投票法 Moore Voting,需要 O(n) 的时间和 O(1) 的空间,比前一种方法更好。这种投票法先将第一个数字假设为过半数,然后把计数器设为1,比较下一个数和此数是否相等,若相等则计数器加一,反之减一。然后看此时计数器的值,若为零,则将下一个值设为候选过半数。以此类推直到遍历完整个数组,当前候选过半数即为该数组的过半数。不仔细弄懂摩尔投票法的精髓的话,过一阵子还是会忘记的,首先要明确的是这个叼炸天的方法是有前提的,就是数组中一定要有过半数的存在才能使用,下面来看本算法的思路,这是一种先假设候选者,然后再进行验证的算法。现将数组中的第一个数假设为过半数,然后进行统计其出现的次数,如果遇到同样的数,则计数器自增1,否则计数器自减1,如果计数器减到了0,则更换下一个数字为候选者。这是一个很巧妙的设定,也是本算法的精髓所在,为啥遇到不同的要计数器减1呢,为啥减到0了又要更换候选者呢?首先是有那个强大的前提存在,一定会有一个出现超过半数的数字存在,那么如果计数器减到0了话,说明目前不是候选者数字的个数已经跟候选者的出现个数相同了,那么这个候选者已经很 weak,不一定能出现超过半数,此时选择更换当前的候选者。那有可能你会有疑问,那万一后面又大量的出现了之前的候选者怎么办,不需要担心,如果之前的候选者在后面大量出现的话,其又会重新变为候选者,直到最终验证成为正确的过半数,佩服算法的提出者啊,代码如下:
C++ 解法一:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = 0, cnt = 0;
for (int num : nums) {
if (cnt == 0) {res = num; ++cnt;}
else (num == res) ? ++cnt : --cnt;
}
return res;
}
};
Java 解法一:
public class Solution {
public int majorityElement(int[] nums) {
int res = 0, cnt = 0;
for (int num : nums) {
if (cnt == 0) {res = num; ++cnt;}
else if (num == res) ++cnt;
else --cnt;
}
return res;
}
}
下面这种解法利用到了位操作 Bit Manipulation 来解,将这个大多数按位来建立,从0到31位,每次统计下数组中该位上0和1的个数,如果1多,那么将结果 res 中该位变为1,最后累加出来的 res 就是过半数了,相当赞的方法,参见代码如下:
C++ 解法二:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = 0, n = nums.size();
for (int i = 0; i < 32; ++i) {
int ones = 0, zeros = 0;
for (int num : nums) {
if (ones > n / 2 || zeros > n / 2) break;
if ((num & (1 << i)) != 0) ++ones;
else ++zeros;
}
if (ones > zeros) res |= (1 << i);
}
return res;
}
};
Java 解法二:
public class Solution {
public int majorityElement(int[] nums) {
int res = 0, n = nums.length;
for (int i = 0; i < 32; ++i) {
int ones = 0, zeros = 0;
for (int num : nums) {
if (ones > n / 2 || zeros > n / 2) break;
if ((num & (1 << i)) != 0) ++ones;
else ++zeros;
}
if (ones > zeros) res |= (1 << i);
}
return res;
}
}
Github 同步地址:
https://github.com/grandyang/leetcode/issues/169
类似题目:
Majority Element II
参考资料:
https://leetcode.com/problems/majority-element/
https://leetcode.com/problems/majority-element/discuss/51613/O(n)-time-O(1)-space-fastest-solution
https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations
https://leetcode.com/problems/majority-element/discuss/51611/Java-solutions-(sorting-hashmap-moore-voting-bit-manipulation).
https://leetcode.com/problems/majority-element/discuss/51828/C++-solution-using-Moore's-voting-algorithm-O(n)-runtime-comlexity-an-no-extra-array-or-hash-table
来源:https://www.cnblogs.com/grandyang/p/4233501.html
猜你喜欢
- 本文介绍为了实现高效并发,虚拟机对 synchronized 做的一系列的锁优化措施高效并发是从 JDK5 升级到 JDK6 后一项重要的改
- 前言自从用了SpringBoot,个人最喜欢的就是SpringBoot的配置文件了,和Spring比起SpringBoot更加灵活,修改的某
- SpringBoot下载Excel文件文件损坏我把模板文件放在了resources目录下maven插件打包项目的时候,默认会压缩resour
- PDF文件和图片文件,这是两种完全不一样的格式,可是有的时候这两种格式却是有相互转换的需要,大家在工作中遇到PDF文件转图片文件的问题时是怎
- 引入线程是为了减少程序在并发执行时所付出的时空开销。属性:轻型实体。它不拥有系统资源,只是有一点必不可少的、能保证独立运行的资源。独立调度和
- 在一些特定的 App 里,我们不希望手机横屏的时候,App 发生旋转,比如微信,企业微信都是这样的。代码可以这样设定:import '
- 打个比方:一个object就像一个大房子,大门永远打开。房子里有很多房间(也就是方法)。这些房间有上锁的(synchronized方法),
- 问题org.apache.ibatis.binding.BindingException: Invalid bound statement
- mybatis的映射文件写法多种多样,不同的写法和用法,在实际开发过程中所消耗的开发时间、维护时间有很大差别,今天我就把我认为比较简单的一种
- Java阻塞队列阻塞队列和普通队列主要区别在阻塞二字:阻塞添加:队列已满时,添加元素线程会阻塞,直到队列不满时才唤醒线程执行添加操作阻塞删除
- 目录一 、EasyExcel简介二、常用注解三、依赖四、监听五、接口导入Excel六、接口 导出Excel (HttpServletResp
- 异常处理机制已经成为判断一门编程语言是否成熟的标准之一,其对代码的健壮性有很大影响。一直以来异常处理使用不是很得心应手,今天对异常进行了较为
- 1、什么是反射?在java开发中有一个非常重要的概念就是java反射机制,也是java的重要特征之一。反射的概念是由Smith在1982年首
- 序言在flutter开发中,我们使用 bloc 框架,基于状态变更进行响应式开发。本篇文章,小轰将 bloc 核心业务块进行拆解简化,聊一聊
- 本文实例为大家分享了SpringMVC实现上传下载文件的具体代码,供大家参考,具体内容如下一、SpringMVC专门提供了CommonsMu
- 目录说明使用常见问题No such instance field: 'logger2'说明logback作为log4j的替代
- 这一篇网络爬虫的实现就要联系上大数据了。在前两篇java实现网络爬虫和heritrix实现网络爬虫的基础上,这一次是要完整的做一次数据的收集
- 首先我们应该清楚的是JDK1.6和JDK1.7中String类的intern方法还是有差别的: JDK1.6中的int
- 看门见山1.java中replace API:replace(char oldChar, char newChar):寓意为:返回一个新的字
- 本文实例展示了Activiti流程图查看的实现方法,具体步骤如下所示:1、测试用例查看图片代码如下:public void viewImag