- 浏览: 1665385 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (335)
- uml (11)
- java (318)
- python (11)
- socket (2)
- ant (1)
- data structures (58)
- algorithms (67)
- concurrency (16)
- multithreading (16)
- mysql (2)
- ubuntu (2)
- c语言 (1)
- lucene (0)
- elasticsearch (0)
- django (1)
- 读书 观点 (2)
- 读书 (4)
- 观点 (4)
- collections (8)
- nio (1)
- io (2)
- 系统集成 (1)
- activemq (2)
- restful (0)
- web service (0)
- HttpClient (1)
- serializable (0)
- annotation (1)
- jdbc (3)
- classloader (0)
- regular expression (1)
- jpa (4)
- jvm (0)
- reflection (1)
- commons-pool2 (2)
- javamail (1)
- velocity (1)
- mathematics (3)
- graph (13)
- LeetCode (159)
- scala (0)
- spring (24)
- maven (5)
- spring batch (1)
- quartz (2)
- IOC (2)
- ORM (3)
- hibernate (2)
- aop (4)
- redis (0)
- zookeeper (0)
- spring mvc (4)
- ELK (1)
- string (1)
- gradle (1)
- mybatis (5)
- docker (0)
- servlet (0)
- log4j2 (1)
- html (0)
- css (0)
最新评论
-
nucleus:
貌似是因为图片的路径是http的缘故:http://dl2.i ...
spring container 实现分析:BeanWrapper -
nucleus:
nucleus 写道BeanWrapper这一块相关的类结构如 ...
spring container 实现分析:BeanWrapper -
nucleus:
BeanWrapper这一块相关的类结构如下图:文中提到的上述 ...
spring container 实现分析:BeanWrapper -
leshy:
inventory.sort(Comparator.compa ...
java8 lambda表达式学习总结 -
Leisurez:
di1984HIT 写道xuexile~hahaha~
activemq的几种基本通信方式总结
问题描述
在一个规模为N的数组A中,所谓的Majority元素就是指出现次数大于N/2的元素(因而最多只有一个这种元素)。比如数组
3, 3, 4, 2, 4, 4, 2, 4, 4 中间有Majority元素4。而数组3, 3, 4, 2, 4, 4, 2, 4则没有majority元素。需要一个算法,如果majority元素存在的话,就找出来,如果不存在,则给出报告。
下意识解法
通过这个问题,我们可以很快得出一个如下的方法。就是首先定义一个HashMap,里面存放数组里面的每个元素以及出现的次数。可以通过两个过程来做。
第一步是映射,将每个元素放进去,如果HashMap里面已经有元素了,则该元素对应的出现次数加一,否则新增加该元素,出现的次数设置为1.
第二步就是遍历整个HashMap,判断是否找到出现次数大于数组长度一半的。如果有,则返回该元素以及出现的次数。否则显示没有该元素。
详细的代码如下:
import java.util.HashMap; import java.util.Map; public class MaxFind { private int maxValue; private int occurence; private int[] array; private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); public MaxFind(int[] array) { this.array = array; } public void map() { if(array == null || array.length == 0) return; for(int i = 0; i < array.length; i++) { if(map.containsKey(array[i])) { int key = array[i]; map.put(key, map.get(key) + 1); } else map.put(array[i], 1); } } public int find() { this.occurence = 0; getValueAndOccurence(); if(this.occurence > array.length / 2) return this.maxValue; else return -1; } private void getValueAndOccurence() { for(Map.Entry<Integer, Integer> entry : map.entrySet()) { if(entry.getValue() > this.occurence) { this.occurence = entry.getValue(); this.maxValue = entry.getKey(); } } } public static void main(String[] args) { int[] array0 = {3, 3, 4, 2, 4, 4, 2, 4, 4}; int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9}; MaxFind finder = new MaxFind(array0); finder.map(); if(finder.find() > 0) System.out.println(finder.find()); } }
分析
整体的代码实现采用一种相对OO一点的方式,因为两个方法都需要访问同一个数组和HashMap,可以将数组和HashMap作为类的成员。另外,HashMap的泛型参数必须为Integer,后面比较的时候会自动的装箱和拆箱。
这个方法的时间复杂度为O(N),因为要用到一个额外的HashMap,所以存储的空间复杂度也是O(N).
总的来说,这个方法很简单,没多少好说的。
进一步的要求
现在,我们看看是否还有进一步可以改进的地方。如果要求空间复杂度为O(1)呢?是否有方法?
分析
这个问题更苛刻的一点在于原来的办法可以用一个HashMap来存放统计结果。现在只能允许用O(1)的空间意味着只能用一个普通的数值变量来帮助解决问题。
这个时候就需要根据问题本身来进一步考虑一下。我们可以看到,如果存在一个majority元素的话,那么肯定一半多的元素都是这一个。我们考虑一种抵消的策略。如果该元素去和所有其他的元素比较,如果不同的都抵消的话,那么剩下的这个元素肯定就是majority元素。那么,具体的抵消步骤该怎么走呢?何况一开始我们也不知道哪个元素是majority元素。
进一步分析
假设我们一开始从数组的开头,碰到某个元素的时候,就设置该元素为当前元素。当前出现的次数为1.后面,如果接着碰到的元素和该元素相同,则当前次数加1,否则减1.如果当前出现的次数为0,则表示当前元素不确定。如果结合我们有majority元素这个前提的话,必然最后的结果是大于0的,而且最终获取到的值就是majority元素。
但是,这种分析还存在一个问题。我们考虑的是majority元素存在的情况。如果majority元素不存在,也有可能出现最终元素出现次数大于0的情况。比如说如下的序列: 1, 1, 1, 2, 2, 2, 3。 这个序列没有majority元素,但是可以按照前面方法得到出现次数大于0的数字3.
很显然,数组中存在majority元素必然可以推出按照我们的方法得到的结果。但是按照我们的方法得到的结果却不能推出数组中存在majority元素。我们的方法只是判断的必要条件。
既然该方法不够充分,我们就还需要进一步的验证。接下来的步骤可以非常简单。我们再一次遍历这个数组,只要找按照前面我们的方法推出来的这个majority元素的次数,如果结果确实> N/2,则这个元素就是我们找到的。否则就没有找到。
至此,我们整个过程就整理出来了。概括一下的话可以分为两个步骤:
1. parse阶段
通过一个抵消的过程遍历数组,得到一个最终出现次数不为0的元素。如果出现的元素为0,则表明没有majority元素。
2. find阶段
按照前面找到的元素,到数组里面核对一下。
具体实现的代码如下:
public class Majority { private static int count; private static int currentValue; public static void parse(int[] array) { if(array == null || array.length == 0) return; count = 1; currentValue = array[0]; for(int i = 1; i < array.length; i++) { if(array[i] == currentValue) count++; else count--; if(count == 0) currentValue = array[i]; } } public static boolean find(int[] array) { if(count == 0) return false; count = 0; for(int i = 0; i < array.length; i++) { if(array[i] == currentValue) count++; } if(count > array.length / 2) return true; else return false; } public static void main(String[] args) { int[] array1 = {1, 2, 3, 4, 5}; int[] array2 = {1, 2, 2}; int[] array3 = {1, 2, 2, 2, 3, 4}; // for array1 case 1 parse(array1); if(find(array1)) System.out.println("value:" + currentValue + "\tcount:" + count); else System.out.println("No majority value found."); // case 2 parse(array2); if(find(array2)) System.out.println("value:" + currentValue + "\tcount:" + count); else System.out.println("No majority value found."); // case 3 parse(array3); if(find(array3)) System.out.println("value:" + currentValue + "\tcount:" + count); else System.out.println("No majority value found."); } }
该算法需要遍历数组两次,总的时间复杂度为O(N) ,空间复杂度为O(1)。
总结
寻找majority元素的方法还有其他的。比如说,先将元素排序,然后再进行判断。因为如果有majority元素的话,取数组中间点的那个元素即为所要找的那个。不过这种方法首先排序就需要O(NlogN)的时间复杂度,并不是很理想。
至于我们那个分两次遍历数组的方法,关键在于利用majority元素的特性进行抵消。
参考资料
A linear time majority vote algorithm
发表评论
-
spring源代码分析:aop的实现
2018-10-03 23:32 682简介 在之前的文章里我们讨论过一些程序构建Pro ... -
java annotation基础
2018-06-30 16:41 830简介 之前有一篇简短的文章讨论过annotati ... -
spring源代码分析:annotation支持的实现
2018-09-03 23:31 2450简介 在之前的文章里,我们讨论了spring I ... -
spring container 实现分析:BeanFactory and ApplicationContext
2018-06-02 18:29 1396简介 在之前的文章里,我们讨论过作为spring ... -
spring aop: ProxyFactory
2018-04-30 16:45 779简介 在之前的文 ... -
日志与log4j2的配置和应用总结
2018-02-15 15:47 12184简介 通常我们在日常的应用开发中,日志起到一个非 ... -
Java servlet学习总结
2018-01-02 21:14 0简介 应用系统架构的演化(从CS到BS) ... -
spring container 实现分析:BeanWrapper
2018-02-19 18:10 1849简介 在之前的一篇文章里, 我们基于《Exper ... -
spring propertyeditor
2017-10-26 09:17 0pro spring 5 chapter 4, page ... -
spring bean life cycle
2018-02-25 13:30 862简介 在使用spring bean的过程中,有一个 ... -
spring container的设计与实现分析
2017-10-08 21:31 2644简介 在之前的一 ... -
jdbc数据访问的封装和演化
2017-09-16 17:00 2591简介 在使用传统jdbc的方式来访问数据的时候, ... -
Boyer Moore算法分析总结
2017-03-31 18:42 3477简介 在之前的文章里,对于字符串的搜索算法,我曾 ... -
mybatis学习总结:mybatis和spring, spring boot的集成
2017-03-04 18:07 2456简介 在前面的讨论里已经提到了mybatis的各种配置 ... -
mybatis学习总结:annotation与xml结合示例
2017-02-25 21:09 3642简介 在之前的文章里讨论过mybatis纯xml或者 ... -
mybatis学习总结:对象关系映射的xml配置实现
2017-02-19 23:03 3999简介 在之前的文章里已经讨论过mybatis的基本配 ... -
mybatis学习总结:annotation示例改进
2017-01-24 09:06 3382简介 在前一篇文 ... -
mybatis学习总结:基础示例
2017-01-21 23:30 838简介 mybatis是一个比较流行的ORM框架, ... -
gradle学习总结
2016-12-18 21:01 4525简介 Java的自动化构建工具比较多,从最开始的an ... -
String sort的几种方法
2016-10-16 23:07 2107简介 在之前的一 ...
相关推荐
k-majority聚类是kmeans聚类的一种形式,主要改变了计算距离的方法,将欧式距离改为majority判断方法。
寻找多数元素。用递归算法MAJORITY实现多数的寻找,其中调用candidate(m)函数。
如果前面查找了 i 个元素,且 cnt == 0,说明前 i 个元素没有 majority,或者有 majority,但是出现的次数少于 i / 2 ,因为如果
finding a majority among n votes.pdffinding a majority among n votes.pdffinding a majority among n votes.pdffinding a majority among n votes.pdfv
Leetcode 169题 Majority Element 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-...
用于处理标签噪声的matlab代码,label noise,集成学习
C语言写的寻找大数元素算法 C语言写的寻找大数元素算法 C语言写的寻找大数元素算法
findMajority 函数用于寻找数组中的众数,利用了 Boyer-Moore Majority Vote 算法。 算法的核心思想是遍历数组,通过计数器来记录当前的众数和出现次数。 如果当前元素与众数相同,则计数器加一;否则计数器减一。当...
三人表决器 三种不同的描述方式 用于进行三人的投票表决
该压缩文件包含4个txt文件,...每个txt中每行为一个数字,txt的所有行作为输入数组。各文件的数据量如下: data_1015.txt:1999999行; data_1015l.txt:99999行; dataset1.txt:100000行; dataset2.txt:500000行。
基于Majority逻辑门映射的电路面积优化
最终的仿真测试表明:结合majority和median表决系统是一种可行的方法,能 够提高表决系统输出正确率;错误率虽然有小幅增加,但能够有效改善 majority无法输出的情况,同时正确率有一定程度的提高。本文提出的表决算法...
leetcode添加元素使和等于 本项目为Njueers所共享 仓库内容主要为平时刷题的submit、遇到的一些经典题解、...II,类似求一个数组中,超过一定重复次数的数,可以考虑摩尔投票算法 2019/07/17 新增 307. Range Sum Que
使用matlab实现多数投票,可用于高光谱图像处理
最近邻学习算法,Python实现,最近邻规则分类
多种经典集成学习算法的matlab实现,包括adaboost、bagging、majority、随机森林等
Hard-Information Bit-Reliability Based Decoding Algorithm for Majority-Logic Decodable Nonbinary LDPC Codes
查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118.Pascal's Triangle -> 理解结构并做167 Two Sum II - 输入数组已排序:使用排序数组的条件,使用前后两个指针35.Search ...
两个数组的简单交集 00.00相同的树 44.8% Easy 171 Excel Sheet 列号 44.5% Easy 387 字符串中的第一个唯一字符 44.4% Easy 242 Valid Anagram 44.2% Easy 409 最长回文 44.1% Easy 169 Majority 元素 44.0% Easy ...
[除Self之外的数组乘积](md/除Self.md之外的数组乘积) - 2015-10-23 [删除链表中的节点](md/删除链表中的节点.md) - 2015-10-23 [二叉树的最低公共祖先](md/二叉树的最低公共祖先.md) - 2015-10-23 [二叉搜索树的...