作者:陈太汉
算法--找出数组中出现次数超过一半的数
每当我看到经典的算法题,就怀念高中,感觉很多算法题就是高中的题目,谁叫哥只读了个专科,高数基本相当没学。
有空要看看高数啊,想当年数学那是相当的......
方法一
第一个想到的方法是见一个二维数组,一维存数组中的数据,二维存这个数出现的次数。出现次数最多的那个数就是要找的那个数
由于某个数出现的次数超过数组长度的一半,所以二维数组的长度只需要这个数组的一半。代码实现如下,
当然这个方法很糟糕,时间复杂度和空间复杂度都比较大,想练手的我还是写了一下。
方法二
将数组排序,最中间的那个数就是您要找的数。
如果出现最多的那个数是最小的,那么1至(n+1)/2都是那个数
如果出现最多的那个数是最大的,那么(n-1)/2至n都是那个数
如果不是最小也不是最大,当这个数由最小慢慢变成最大的最大的数时,你会发现中间的那个数的值是不变的。
综上所述,中间的那个数就是你要找的那个数。
时间复杂度就是你排序用的时间。排序真的不想写了(可以参考《我的另一篇博客》)。大家都知道排序还是相当费时的,当然这个方法还是不太好。
方法三
这个方法借用了别人的思路。
在这里我做一下简单的分析。
这个算法的时间复杂度是O(n),另外用了两个辅助变量。
k用于临时存储数组中的数据,j用于存储某个数出现的次数。
开始时k存储数组中的第一个数,j为0,如果数组出现的数于k相等,则j加1,否则就减1,如果j为0,就把当前数组中的数赋给k
因为指定的数出现的次数大于数组长度的一半,所有j++与j--相抵消之后,最后j的值是大于等于1的,k中存的那个数就是出现最多的那个数。
下面这个算法只适合数组中数组中某个数的出现次数超过数组长度一半的数组,符合题意。
分享到:
相关推荐
数组中出现次数超过一半的数字.md
算法-数据结构- 树状数组.rar
Giovanni Manzini and Paolo Ferragina 吸取了前人多种经验,结合n个算法,组建了最快的sa构建法.2005年新出的算法.是GNU开源项目,竞赛中 1000万的数据是 1 s,文件相当多,不能写在博客里,linux源码可以看: ...
主要介绍了PHP实现找出数组中出现次数超过数组长度一半的数字算法,涉及php数组的遍历、统计、判断等相关操作技巧,需要的朋友可以参考下
分治算法求n个数的数组中找出第二个最大元素
算法-数据结构之【数组和广义表】复习题.rar
1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,多和面试官沟通,然后开始做一些整体的设计和规划。不要急于提交,自己测试几个用例避免错误...
学习笔记[韩顺平老师讲的数据结构和算法];数据结构和算法之稀疏数组。个人的一个理解。
算法#26--查找字符串数组中最长的公共前缀Write a function to find the longest common prefix string
题:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 解题思路...
57春节7天练---Day-1:数组和链表 数组和链表.pdf
给定一个整形数组和一个数字s,找到数组中最短的一个连续子数组,使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值public int minS
python算法-数组和链表 数组和链表.pdf
算法-数组排序 按数组内数字大小排序 取得最大值或最小值.rar
算法中数据结构的一个重要的应用,树状数组的两个应用。写的比较详尽
华为od算法题-组装新的数组-Java解法
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
js代码-初级算法-旋转数组