Leetcode-面试题 17.10. 主要元素(摩尔投票法)

面试题 17.10. 主要元素 (摩尔投票法)

  • 方法一:Map方法(不满足题目空间复杂度)
  • 方法二:摩尔投票法

面试题 17.10. 主要元素
题目链接:https://leetcode-cn.com/problems/find-majority-element-lcci/

方法一:Map方法(不满足题目空间复杂度)

class Solution {
public int majorityElement(int[] nums) {
      Map<Integer,Integer> map=new HashMap<>();
      int len=nums.length;
      int find=-1;
      for (int tmp:
           nums) {
          map.put(tmp,map.getOrDefault(tmp,0)+1);
          if (map.get(tmp)>len/2){
              find=tmp;
              System.out.println(find);
          }
      }
      return find;
  }
}

方法二:摩尔投票法

学习链接:https://www.zhihu.com/question/49973163

class Solution {
  public int majorityElement(int[] nums) {
            int tmp=nums[0];
            int count=1;
            for (int i = 1; i <nums.length ; i++) {
                if (nums[i]==tmp){
                    count++;
                }else {
                    count--;
                }

                if (count==0){
                    tmp=nums[i];
                    count=1;
                }
           }
            int num=0;
            for (int w:nums){
                if (w==tmp){
                    num++;
                }
            }
            return num>nums.length/2?tmp:-1;

       }
}

持续更新中…

热门文章

暂无图片
编程学习 ·

springboot+idea+bootstrap的带有图片的表格编辑操作

前面已经写了 批量导入,图片显示,现在写的是批量修改,后面会写用echarts+springboot 做折线图,有时间贴上 1、jsp代码如下,编辑按钮formatter: function (value, row, index) {var edit = <input class="btn btn-primary" type="button" value=&qu…
暂无图片
编程学习 ·

【Flutter 实战】简约而不简单的计算器

老孟导读:这是 【Flutter 实战】组件系列文章的最后一篇,其他组件地址:http://laomengit.com/guide/widgets/Text.html,接下来将会讲解动画系列,关注老孟,精彩不断。先看一下效果:大家学习UI编程语言时喜欢用哪个 App 当作第一个练手的项目呢?,我喜欢使用 计算器 ,可…
暂无图片
编程学习 ·

省市区三级行政区数据获取和GeoJson地图下载

文章目录1.背景2.行政区域数据获取3.获取GeoJson数据 1.背景 项目中用到省市区三级的行政区划的选择,在网上找到的数据与最新的行政区域划分不一致,也难以确认数据的完成性。 基于echarts完成数据地区分布图时,需要提供地区对应的geoJson格式地图。 2.行政区域数据获取 高德…
暂无图片
编程学习 ·

如何将PDF转换成jpg图片?教你2种免费方法

如何将PDF格式的文件转换成JPG图片?有时为了方便需要将PDF转成图片来使用,直接截图不仅耗费时间,而且像素很不清晰,有没有其他方便快捷转出高清图片的方法呢? 方法1: 这个方法最方便就在于不用下载安装软件,甚至都不需要注册登录,只要有网络,手机和电脑都能快速操作完…
暂无图片
编程学习 ·

坚强奋斗的后浪们,后浪们的逆风翻盘之路。

逆风5.4日B站播出了后浪,视频伴随着激情澎湃的音乐、华丽无比的台词、精英人士的代言,可以说很振奋人心。但是观看后,网上却有着两种不同的声音,分别是乐观与悲观。当然伴随着疫情肆虐,悲观的声音反而是最响亮。90后们更是看的焦躁不安、时逢逆风,如何翻盘? 逆风论点:通…
暂无图片
编程学习 ·

无线传输技术有哪些?

什么是ZigBee? ZigBee,也称紫蜂,是一种低速短距离传输的无线网上协议,底层是采用IEEE802.15.4标准规范的媒体访问层与物理层。主要特色有低速、低耗电、低成本、支持大量网上节点、支持多种网上拓扑、低复杂度、快速、可靠、安全。 三大特征、八大优势 特征一 ZigBee能源消…
暂无图片
编程学习 ·

Vue动态缓存页面

原理通过keep-alive标签的include属性及vuex完成 需求说明:A页面到B页面需要缓存,A页面到C页面不需要缓存 所要缓存页面的顶级出口 <keep-alive :include="kpAlive"><router-view/> </keep-alive><script> export default {computed: {/**…
暂无图片
编程学习 ·

双亲委派模型

原理 双亲委派模式是在Java 1.2后引入的,其工作原理的是,如果一个类加载器收到了类加载请求,它并不会自己先去加载,而是把这个请求委托给父类的加载器去执行,如果父类加载器还存在其父类加载器,则进一步向上委托,依次递归,请求最终将到达顶层的启动类加载器,如果父类加…
暂无图片
编程学习 ·

每天一刷20200701

今天7.1号也要加油哦 问题 题目描述 实现删除字符串中出现次数最少的字符,若多个字符出现次数一样,则都删除。输出删除这些单词后的字符串,字符串中其它字符保持原来的顺序。 注意每个输入文件有多组输入,即多个字符串用回车隔开 输入描述: 字符串只包含小写英文字母, 不考…
暂无图片
编程学习 ·

“百度大脑EasyDL经典版”拍了拍你,真实的产业应用get了吗?

在现有业务或方案的基础上,企业如何通过引入AI能力真正做到在降低成本的同时提升效率?质检流水线中,检测人员注意力与体力不支导致的低效、价格高昂的智能检测设备、千变万化的瑕疵形态都迫使企业投入更多成本;电网户外巡检中,越来越密集的电网分布、安全指标提升带来的巡…
暂无图片
编程学习 ·

Maven常用命令总结大纲

Maven常用命令总结大纲一、maven的作用二、maven的下载(国内镜像),安装,配置流程1、打开https://maven.apache.org/并点击下载2、点击箭头所指处的Zip文件3、解压并配置环境变量4、配置国内镜像(阿里云镜像)三、常见的maven命令总结四、多模块springboot项目中的maven打包方式…
暂无图片
编程学习 ·

亚马逊ERP系统独立部署OEM定制无限开账号

马逊无货源模式,和传统无货源模式操作一样!需要咱们开店利用软件去采集商品,上传到咱们店铺,有订单了去上家拍下,发到深圳的中转仓,进行商品检测二次包装,发往国外!赚取汇率差! 要做亚马逊无货源模式,那么亚马逊ERP也是必须用的!市场erp已经出现很多,但是真正做技术…
暂无图片
编程学习 ·

结构体学生信息输入

不知不觉学到第七章结构体了,这一章开始到后面的章节网上的免费课程就越来越少了。每次有不会的只能各种百度,心累。。。但还是会坚持的!!! 记录第7章课后习题第3题: 题目:编写一个函数print,打印一个学生的成绩数组,该数组中有5个学生的数据,每个学生的数据包括num(学…
暂无图片
编程学习 ·

springboot静态资源无法加载最后原因竟然是拦截器没有生效

今天打开项目,发现页面的样式没了,用F12调试,果不其然,css,js等样式没有加载成功 后面看控制台发现报 No mapping for GET 静态资源。 很明显,访问静态资源的请求被springboot拦截了。 然后我又看自己写的拦截器 @Overridepublic void addInterceptors(InterceptorRegist…
暂无图片
编程学习 ·

selenium+ChromeDriver+java爬虫初探

selenium+ChromeDriver+java爬虫初探seleniumChromeDriver简单的demo selenium 自动化测试工具,可以完全模拟人的行为。我们可以用它来打开浏览器,访问指定URL,并且定位到具体的按钮,点击触发事件等等。ChromeDriver selenium和谷歌浏览器交互,需要这个驱动。下载地址(ht…
暂无图片
编程学习 ·

jdbcTemplate.queryForObject 没查到抛异常

当结果集合的size为0或者大于1时,就会抛出异常。 解决方法有两个: (1)通过修改数据库:删除数据库中对应名称(column)相同的记录,留下只剩"1"条。 (2)通过更换方法:使用query方法返回list对象(该方法能返回所有查询记录)