算法面试题-leetcode学习之旅(一)

时间:2022-12-23 19:22:14

问题描述

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.

解决思路:

算法面试题-leetcode学习之旅(一)

推荐算法:

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学习之旅(一)的更多相关文章

  1. 二叉树的最大深度算法面试题-leetcode学习之旅(3)

    标题 Maximum Depth of Binary Tree 描述 The maximum depth is the number of nodes along the longest path f ...

  2. 算法面试题-leetcode学习之旅(二)

    题目: Given a non-negative integer num, repeatedly add all its digits until the result has only one di ...

  3. LeetCode 算法面试题汇总

    LeetCode 算法面试题汇总 算法面试题 https://leetcode-cn.com/problemset/algorithms/ https://leetcode-cn.com/proble ...

  4. 【BAT经典算法面试题系列】求和为n的连续正整数

    马上就要到9月份了,意味着一年一度的秋招就要开始了,相信不论是正在实习的童鞋还是马上就要找工作的童鞋,BAT无疑是国内的"明星企业",是每个学计算机的小伙伴们心之向往的企业,但是呢 ...

  5. Java算法面试题(史上最强、持续更新、吐血推荐)

    文章很长,建议收藏起来,慢慢读! 疯狂创客圈为小伙伴奉上以下珍贵的学习资源: 疯狂创客圈 经典图书 : <Netty Zookeeper Redis 高并发实战> 面试必备 + 大厂必备 ...

  6. 算法面试题:一个List&lt&semi;Student&gt&semi;,要求删除里面的男生,不用Linq和Lamda,求各种解,并说明优缺点!

    算法面试题:一个List,要求删除里面的男生,不用Linq和Lamda,求各种解,并说明优缺点! 解题思路 这是群里某位小伙伴去面试碰到的面试题,从题目本身来看,面试官应该是要考察面试者对泛型 Lis ...

  7. Twitter算法面试题详解(Java实现)

    最近在网上看到一道Twitter的算法面试题,网上已经有人给出了答案,不过可能有些人没太看明白(我也未验证是否正确),现在给出一个比较好理解的答案.先看一下题目. 图1 先看看图图1.可以将方块看做砖 ...

  8. 算法实践——Twitter算法面试题(积水问题)的线性时间解法

    问题描述:在下图里我们有不同高度的挡板.这个图片由一个整数数组所代表,数组中每个数是墙的高度.下图可以表示为数组(2.5.1.2.3.4.7.2).假如开始下雨了,那么挡板之间的水坑能够装多少水(水足 ...

  9. 华为Python 算法面试题

    华为算法面试题 """ 算法题: 提供一个序列,完成对这个序列的分割.要求分割后的两个序列彼此差值最小 实现函数,返回两个序列 """ de ...

随机推荐

  1. 数据字典生成工具之旅&lpar;5&rpar;:DocX组件读取与写入Word

    由于上周工作比较繁忙,所以这篇文章等了这么久才写(预告一下,下一个章节正式进入NVelocity篇,到时会讲解怎么使用NVelocity做一款简易的代码生成器,敬请期待!),好了正式进入本篇内容. 这 ...

  2. PLoP(Pattern Languages of Programs,程序设计的模式语言)

    2014/8/1 12:24:21潘加宇 http://www.umlchina.com/News/Content/340.htmPloP大会2014即将举行 PLoP(Pattern Languag ...

  3. 在C&num;中利用Nuget包使用SQLite数据库和Linq to SQLite

    本来是学习在VB中使用SQLite数据库和Linq to SQLite,结果先学习到了在C#中使用SQLite数据库和Linq to SQLite的方法,写出来与大家共同学习.(不知道算不算不务正业) ...

  4. &lt&semi;item&period;&period;&period;&sol;&gt&semi;元素可指定如下常用属性

    android:id:为菜单项指定一个唯一表实.android:title:指定菜单项的标题.android:icon:指定菜单项的图标.android:alphabeticShortcut:为菜单项 ...

  5. HTML——JavaScript简介

    一.简介: JavaScript是个脚本语言,需要有宿主文件,他的宿主文件是HTML文件. JavaScript 是属于 web 的语言,它适用于 PC.笔记本电脑.平板电脑和移动电话. JavaSc ...

  6. C&plus;&plus;&lowbar;知识点&lowbar;结构体&sol;枚举&sol;联合

    //C++中结构体的不同之处 #include <iostream> #include <string> using namespace std; int main(void) ...

  7. PHP基础入门(三)---PHP函数基础

    PHP基础入门(三)---函数 今天来给大家分享一下PHP的函数基础.有了前两章的了解,想必大家对PHP有了一定的基础了解.想回顾前两章的朋友可以点击"PHP基础入门(一)"&qu ...

  8. JMeter通过beanShell脚本生成随机手机号

    package xnzx; /** * @author xn088587 * */ public class getTel{ public static int getNum(int start,in ...

  9. js 时间戳转换为&OpenCurlyQuote;yyyy-MM-dd hh&colon;mm’格式&lpar;es6语法&rpar;

    function formatDate(date,fmt) { if(/(y+)/.test(fmt)){ fmt = fmt.replace(RegExp.$1,(date.getFullYear( ...

  10. leecode第九题(回文数)

    class Solution { public: bool isPalindrome(int x) { ) return false; ;//这里使用long,也不判断溢出了,反正翻转不等就不是回文 ...