[算法]数组中出现次数超过一半的数字
2023-09-11 14:16:50 时间
题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
思路
这道题最简单的思路就是排序,然后统计每个数字出现的次数,这样时间复杂度是O(nlogn)。
也可以用哈希表进行次数的统计,但是这样最大的空间复杂度是O(n)。
这里提供一种时间复杂度是O(n),空间复杂度是O(1)的解法。
数组中有一个数字出现的数字超过数组长度的一半,也就是说它出现的次数比其他所有数字出现的次数还要多。在遍历数组的时候,保存三个变量,一个是当前元素出现的次数,一个是当前元素,一个是数组中出现次数最多的元素值。当我们遍历到下一个数字的时候,如果下一个数字和当前元素值相等,则次数加1,如果不相等,则次数减1。如果次数为0,则当前元素等于下一个数字,并把次数设为1,最后剩下的那个肯定是出现次数最多的元素,记录出现次数最多的元素值,最后验证是否超过数组一半的数字。
代码
public class Solution { public int MoreThanHalfNum_Solution(int[] array) { int count = 1;//当前元素出现的次数 int number = array[0];//当前的元素 int maxnum = array[0];//数组中出现次数最多的元素值 for (int i = 1; i < array.length; i++) { if(array[i] != number){ count--; if(count == 0){ number = array[i]; maxnum = array[i]; count = 1; } }else{ count++; } } //验证 int sum = 0; for (int i = 0; i < array.length; i++) { if(array[i] == maxnum){ sum++; } } return sum * 2 > array.length ? maxnum : 0; } }
相关文章
- STL_算法_区间的比較(equal、mismatch、 lexicographical_compare)
- 不定长数组取值交叉遍历组合生成算法
- 算法的在线演示网站
- 【算法】【递归与动态规划模块】数组字符串转字母的所有种数
- (《机器学习》完整版系列)第16章 强化学习——16.2 K-摇劈赌博机的贪心算法(赌博当然贪心)
- 背包算法练习--求小于某数字的数组最大和:
- 进程状态转换、CPU调度算法
- Google Earth Engine(GEE)——Landsat 系列卫星及其算法的介绍(新手必备)!
- JavaScript - 数组排序 6 种常见算法
- 基于锁的并发算法 vs 无锁的并发算法
- NLP文本分类入门学习及TextCnn实践笔记——算法实现(四)
- 数组的几种排序算法的实现
- [算法]数组中求出下标不连续的任意个数,使得和最大
- [算法]最大连续子数组和,最长重复子串,最长无重复字符子串
- [算法]快速排序,归并排序,堆排序的数组和单链表实现
- 在opencv3中的机器学习算法
- javascript数据结构与算法:数组
- Python实现的粒子群优化算法
- 数据库的算法
- 137、【贪心算法】leetcode ——406. 根据身高重建队列(多维度贪心)(C++版本)
- 【算法刷题】数组题型及方法归纳
- 华为OD机试 - 停车场最大距离(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -太阳能板最大面积(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -数组排序(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 算法8:巧妙的邻接表(数组实现)
- python实现排序算法
- 【算法专题】使用递归取数组的平均值(向下取整)
- 算法系列整理:查找算法-二分查找
- leetcode算法108.将有序数组转换为二叉搜索树