题目要求: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.
我的解法:
int majorityElement(vector<int> &num) {
int key = num.back();
int k = num.size();
k--;
int i = k-1;
while (i >= k/2)
{
if (num[i] != key)
{
num[i] = num[k-1];
k--;
key = num[k-1];
k--;
i=k-1;
continue;
}
i--;
}
return key;
}
分析:首先要知道一个定理,如果一个序列中存在一个出现率大于1/2的元素,我们记为mE,那么如果去掉这个序列中的两个不相同的元素,新序列中一定存在一个出现率大于1/2的元素,依然是mE。
该算法最差情况需要在i指向第一个元素的时候,也就是算法的复杂度最差是O(n),最好的情况需要n/2。
这个问题还可以直接考虑,通过map来计数,来获取所求的元素。代码如下:
int majorityElement(vector<int> &num) {
map<int, int> count;
for (int i : num)
{
if (++count[i] >= num.size() / 2)
{
return i;
}
}
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
OJ习题.zip
这是洛谷OJ题库导出文件,希望大家下载看看
西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案西南科技大学OJ题答案
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
OJ系统的蓝桥杯题库,http://oj.xpuca.top/,这里有这些题的栗子。
这是聚石塔OJ题库导出文件,希望大家下载看看
HUSTOJ-SAE 安装次数 : 110 本系统为Online Judge 系统,可广泛用于教学、竞赛、招聘等用途。 九度OJ为本系统改造的典型案例。 文档、社区服务见项目首页,http://code.google.com/p/hustoj/ 安装应用 下载应用...
这是大连东软信息学院的内部OJ题库,希望大家下载看看
oj 的c++类与对象之前包括类与对象的全答案
BJFU-OJ实验
OJ基础部分代码 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 ...
华为OJ测试平台的代码集合,可以借鉴代码例子,共同提高。
oj题.zip
课程资源 杭电OJ1000-1099答案 ,仅供参考...
郑州轻工业大学在线评测系统(ZZULIOJ)部分答案。大一上学期自己做的,全部是c语言实现,不一定是最优解仅供参考。希望可以帮助到大家。
登录ssh,执行安装脚本:wget http://dl.hustoj.com/install-ubuntu-bt.shsudo bash install-ubu
八中oj代码
很好的离线题库。。。。。 非常不错北大OJ题目