Majority Element(ARRAY-BINARY SEARCH)
2024-10-13 10:39:34
QUESTION
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-empty and the majority element always exist in the array.
FIRST TRY
每找出两个不同的element,则成对删除。最终剩下的一定就是所求的。
class Solution {
public:
int majorityElement(vector<int> &num) {
int ret;
int nTimes = ;
for(int i = ; i < num.size(); i++){
if(nTimes == )
{
ret = num[i];
nTimes++;
}
else if(ret == num[i]) nTimes++;
else nTimes--; //2 different number, delete
}
return ret;
}
};
Result: Accepted
可扩展到⌊ n/k ⌋的情况,每k个不同的element进行成对删除。
最新文章
- pptpvpn 连接后 无法上外网
- uva133-S.B.S.
- LINQ TO DATATABLE/DATASET基本操作之-简单查询
- 李洪强iOS开发Swift篇---11_变量&;常量&;元组
- LintCode-编辑距离
- redis作为mysql的缓存服务器(读写分离) (转)
- JS达到Web指定保存的和打印功能的内容
- 【高德地图API】从零开始学高德JS API(二)地图控件与插件——测距、圆形编辑器、鼠标工具、地图类型切换、鹰眼鱼骨
- Cdoefroces #354
- 分享几个 git 的使用场景
- 【easy】power of 2,3,4
- (二)类数组对象HTMLCollection
- iis默认文档
- TypeScript作业
- DOS下读取PCI配置空间信息的汇编程序(通过IOCF8/IOCFC)
- 30 C? Go? Cgo!
- MySQL启动项提权
- Boost智能指针——weak_ptr
- Django ORM 查询
- [设计模式-行为型]状态模式(State)
热门文章
- Unreal Engine 4(虚幻UE4)GameplayAbilities 插件入门教程(五)技能属性集(AttributeSet)
- php session保存到memcache或者memcached中
- Logistic回归的两种形式y=0/1,y=+1/-1
- CSS border-right-style属性设置元素的右边框样式
- Python - Django - 登录页面
- python2-python3字符串
- 2013年6月编程语言排行榜,C语言位据第一位
- 75. ID重新走过,备份表
- https Configure a Spring Boot app for HTTPS on Amazon AWS.
- leetcode235