问题描述
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.
解决思路:
推荐算法:
Moore voting algorithm–每找出两个不同的element,就成对删除即count–,最终剩下的一定就是所求的。时间复杂度:O(n)
java实现:
public class Solution {
public int majorityElement(int[] nums) {
//0627
//Moore Voting
int n = nums.length;
int candidate = 0;
int times = 0;
for(int i = 0; i < n; i++){
if(times == 0) candidate = nums[i];
if(nums[i] != candidate){
times--;
} else{
times++;
}
}
return candidate;
//0631
}
}
c实现:
class Solution {
public:
int majorityElement(vector<int> &num) {
int elem = 0;
int count = 0;
for(int i = 0; i < num.size(); i++) {
if(count == 0) {
elem = num[i];
count = 1;
}
else {
if(elem == num[i])
count++;
else
count--;
}
}
return elem;
}
};
算法面试题-leetcode学习之旅(一)的更多相关文章
-
二叉树的最大深度算法面试题-leetcode学习之旅(3)
标题 Maximum Depth of Binary Tree 描述 The maximum depth is the number of nodes along the longest path f ...
-
算法面试题-leetcode学习之旅(二)
题目: Given a non-negative integer num, repeatedly add all its digits until the result has only one di ...
-
LeetCode 算法面试题汇总
LeetCode 算法面试题汇总 算法面试题 https://leetcode-cn.com/problemset/algorithms/ https://leetcode-cn.com/proble ...
-
【BAT经典算法面试题系列】求和为n的连续正整数
马上就要到9月份了,意味着一年一度的秋招就要开始了,相信不论是正在实习的童鞋还是马上就要找工作的童鞋,BAT无疑是国内的"明星企业",是每个学计算机的小伙伴们心之向往的企业,但是呢 ...
-
Java算法面试题(史上最强、持续更新、吐血推荐)
文章很长,建议收藏起来,慢慢读! 疯狂创客圈为小伙伴奉上以下珍贵的学习资源: 疯狂创客圈 经典图书 : <Netty Zookeeper Redis 高并发实战> 面试必备 + 大厂必备 ...
-
算法面试题:一个List<;Student>;,要求删除里面的男生,不用Linq和Lamda,求各种解,并说明优缺点!
算法面试题:一个List,要求删除里面的男生,不用Linq和Lamda,求各种解,并说明优缺点! 解题思路 这是群里某位小伙伴去面试碰到的面试题,从题目本身来看,面试官应该是要考察面试者对泛型 Lis ...
-
Twitter算法面试题详解(Java实现)
最近在网上看到一道Twitter的算法面试题,网上已经有人给出了答案,不过可能有些人没太看明白(我也未验证是否正确),现在给出一个比较好理解的答案.先看一下题目. 图1 先看看图图1.可以将方块看做砖 ...
-
算法实践——Twitter算法面试题(积水问题)的线性时间解法
问题描述:在下图里我们有不同高度的挡板.这个图片由一个整数数组所代表,数组中每个数是墙的高度.下图可以表示为数组(2.5.1.2.3.4.7.2).假如开始下雨了,那么挡板之间的水坑能够装多少水(水足 ...
-
华为Python 算法面试题
华为算法面试题 """ 算法题: 提供一个序列,完成对这个序列的分割.要求分割后的两个序列彼此差值最小 实现函数,返回两个序列 """ de ...
随机推荐
-
数据字典生成工具之旅(5):DocX组件读取与写入Word
由于上周工作比较繁忙,所以这篇文章等了这么久才写(预告一下,下一个章节正式进入NVelocity篇,到时会讲解怎么使用NVelocity做一款简易的代码生成器,敬请期待!),好了正式进入本篇内容. 这 ...
-
PLoP(Pattern Languages of Programs,程序设计的模式语言)
2014/8/1 12:24:21潘加宇 http://www.umlchina.com/News/Content/340.htmPloP大会2014即将举行 PLoP(Pattern Languag ...
-
在C#中利用Nuget包使用SQLite数据库和Linq to SQLite
本来是学习在VB中使用SQLite数据库和Linq to SQLite,结果先学习到了在C#中使用SQLite数据库和Linq to SQLite的方法,写出来与大家共同学习.(不知道算不算不务正业) ...
-
<;item.../>;元素可指定如下常用属性
android:id:为菜单项指定一个唯一表实.android:title:指定菜单项的标题.android:icon:指定菜单项的图标.android:alphabeticShortcut:为菜单项 ...
-
HTML——JavaScript简介
一.简介: JavaScript是个脚本语言,需要有宿主文件,他的宿主文件是HTML文件. JavaScript 是属于 web 的语言,它适用于 PC.笔记本电脑.平板电脑和移动电话. JavaSc ...
-
C++_知识点_结构体/枚举/联合
//C++中结构体的不同之处 #include <iostream> #include <string> using namespace std; int main(void) ...
-
PHP基础入门(三)---PHP函数基础
PHP基础入门(三)---函数 今天来给大家分享一下PHP的函数基础.有了前两章的了解,想必大家对PHP有了一定的基础了解.想回顾前两章的朋友可以点击"PHP基础入门(一)"&qu ...
-
JMeter通过beanShell脚本生成随机手机号
package xnzx; /** * @author xn088587 * */ public class getTel{ public static int getNum(int start,in ...
-
js 时间戳转换为‘yyyy-MM-dd hh:mm’格式(es6语法)
function formatDate(date,fmt) { if(/(y+)/.test(fmt)){ fmt = fmt.replace(RegExp.$1,(date.getFullYear( ...
-
leecode第九题(回文数)
class Solution { public: bool isPalindrome(int x) { ) return false; ;//这里使用long,也不判断溢出了,反正翻转不等就不是回文 ...