博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数组中出现次数超过一半的数字
阅读量:5844 次
发布时间:2019-06-18

本文共 612 字,大约阅读时间需要 2 分钟。

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

思路:1.可以使用快速排序的思路,因为出现次数超过一半的数字肯定是中位数,使用Partition函数划分数组,直到返回一个下标为(length-1)/2的元素即为所求。

           2.如果说一个数字出现次数超过数组长度的一半那么它出现的次数一定是比其他数字出现次数之和还要多的,所以可以使用一个变量来保存数字出现的次数,如果下一个数字与上一个相同则次数加一,否则减一,如果次数为零,则保存这个数字,并把次数设置为1.那么在遍历完整个数组后,最后一次把次数设置为1的元素就是所求的元素。但是这个元素不一定存在所以在最后还需要判断一下。

思路2实现代码:

public class Solution {    public int MoreThanHalfNum_Solution(int [] array) {        if(array == null || array.length == 0)            return 0;                int res = array[0];        int times = 1;                for(int i=1; i

 

转载地址:http://szqcx.baihongyu.com/

你可能感兴趣的文章
log4j日志归档
查看>>
mysql遇见error,1049
查看>>
codevs——2822 爱在心中
查看>>
Python基础班---第一部分(基础)---Python基础知识---认识Python
查看>>
JAVA MAC 配置
查看>>
1134 最长上升子序列 (序列型 DP)
查看>>
js冒泡排序
查看>>
第一次作业 4班卢炳武
查看>>
抽象类的调用
查看>>
使用硬盘,安装双系统,Win7+CentOS
查看>>
Javascript学习总结
查看>>
php 用正则替换中文字符一系列问题解决
查看>>
ActiveMQ应用笔记一:基本概念&安装
查看>>
大话数据结构之四(串)
查看>>
加热炉简是新来的整个系统的板
查看>>
Mockito使用注意事项
查看>>
[LeetCode] Palindrome Linked List 回文链表
查看>>
UVA - 825Walking on the Safe Side(dp)
查看>>
评论:人才流失强力折射出现实畸形人才观
查看>>
git服务器gitlab之搭建和使用--灰常好的git服务器【转】
查看>>