169 Majority Element 求众数 数组中出现次数超过一半的数字
2024-09-05 04:04:34
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且数组中的众数永远存在。
详见：https://leetcode.com/problems/majority-element/description/
Java实现：
方法一：
class Solution {
public int majorityElement(int[] nums) {
int n=nums.length;
if(n==0||nums==null){
return -1;
}
int num=nums[0];
int cnt=1;
for(int val:nums){
if(val==num){
++cnt;
}else{
--cnt;
if(cnt==0){
num=val;
cnt=1;
}
}
}
cnt=0;
for(int val:nums){
if(val==num){
++cnt;
}
}
if(2*cnt>n){
return num;
}
return -1;
}
}
方法二：
class Solution {
public int majorityElement(int[] nums) {
int n=nums.length;
if(n==0||nums==null){
return -1;
}
int low=0;
int high=n-1;
int mid=n>>1;
int index=partition(nums,low,high);
while(index!=mid){
if(index>mid){
high=index-1;
index=partition(nums,low,high);
}else if(index<mid){
low=index+1;
index=partition(nums,low,high);
}
}
int num=nums[mid];
int cnt=0;
for(int val:nums){
if(val==num){
++cnt;
}
}
if(2*cnt>n){
return num;
}
return -1;
}
private int partition(int[] nums,int low,int high){
int pivot=nums[low];
while(low<high){
while(low<high&&nums[high]>=pivot){
--high;
}
nums[low]=nums[high];
while(low<high&&nums[low]<=pivot){
++low;
}
nums[high]=nums[low];
}
nums[low]=pivot;
return low;
}
}
python实现：
参考：http://www.cnblogs.com/grandyang/p/4233501.html
最新文章
- python-操作csv文件
- 2014 Super Training #10 D 花生的序列 --DP
- ExtJs学习笔记之学习小结LoginDemo
- File类的基本操作之读出所有目录路径
- 简单学C——第七天
- React-Native post和get请求
- 基于raw os 的事件触发系统
- Algorithm Part I:Priority Queues
- 【JAVAWEB学习笔记】13_servlet
- 像 npm 一样在 Andriod 项目中引入 Gradle 依赖
- 【ABP框架系列学习】介绍篇(1)
- C++笔记（1）
- 网络唤醒（WOL）全解指南：原理篇
- BAT修改文本内容
- WinForm基于插件开发实现多项配置存储
- C++ 变量默认初始值不确定(代码测试)
- 如何使用KVM 虚拟机安装RHEL7系统
- html form method 属性不支持put,delete请求方式，以及开启spring mvc的rest的方式
- Cookie详解、ASP.NET核心知识（7）
- 完美解决方案：wordpress后台进不去，用户名、密码输入了登陆没有反应（有更新）
热门文章
- Office Adobe Acrobat把PDF转换为Word时候提示不支持的Type2字体怎么办
- 数据结构-二叉树的遍历（类C语言描写叙述）
- IO流（字节流复制）01
- 嵌入式开发之davinci--- 8148 小站信息
- @Html.ValidationMessageFor客户端验证
- extjs grid 列顺序紊乱问题
- 2016/3/31 拾遗 php字符串中 转义字符 “ ’‘ ” ’ “” ‘ " \’ ' ' \‘ " " \" '' \ " " 使用
- Struts2中ValueStack结构和总结
- Codeforces Round #261 (Div. 2)——Pashmak and Graph
- XMU 1607 nc与点对距离 【线段树】