文档章节

找出数组中出现次数大于n/2的元素

I
 Iter_迟cH1
发布于 2016/08/10 15:32
字数 160
阅读 27
收藏 0
public class Solution {
    public int majorityElement(int[] nums) {
        int temp = 0;
        int count = 0;
        for(int i=0;i<nums.length;i++){
            if(count == 0){
                temp = nums[i];
                count++;
            }
            else{
                if(temp == nums[i]){
                    count++;
                }
                else{
                    count--;
                }
            }
        }
        return temp;
    }
}

采用两两抵消的方法,设置一个计数器count。首先令temp等于第一次元素,count为1,如果下一个元素和temp相等,则count++,如果不相等,则count--。如果count等于0,那么temp重新赋值为下一个元素,重复上面的步骤。直到遍历完数组,则剩下的temp一定是数组中出现次数大于n/2的元素。

© 著作权归作者所有

共有 人打赏支持
I
粉丝 0
博文 28
码字总数 4377
作品 0
哈尔滨
1111111111111 算法汇总

如何找到两个相交链表对交点? 如果两个单向链表有公共节点,则两个链表会构成Y型结构,最后一个节点相同 我们可以从头开始遍历两个链表,找到最后一个节点的指针,设为pa,pb。同时记录下两...

素雷
01/03
0
0
169. Majority Element。

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 ......

Leafage_M
01/06
0
0
高效的算法求解一个序列的主元素

题目描述: 已知一个整数序列A={a0,a1,a2,...an-1} 其中0<=ai<n(0<=i<n).若存在 ap1=ap2=...=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素。如 A={0,5,5,3,5,7,5,5},则5为主元素,又如A={......

XJ_hello
2016/12/19
57
0
算法知识梳理(4) - 数组第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 一、概要 本文介绍了有...

泽毛
2017/11/10
0
0
448. Find All Numbers Disappeared in an Array。

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not ap......

Leafage_M
2017/12/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

DeepMind 开源图神经网络的代码

用于支持论文《Relational inductive biases, deep learning, and graph networks》。 github A graph network takes a graph as input and returns a graph as output. The input graph has......

shengjuntu
24分钟前
1
0
python2编码详解、一

以前使用python3没觉的什么,跟着公司使用python2后被编码问题折磨的痛不欲生,好好研究了一下编码问题,参考了很多博文,加入自己的理解,这里只是对编码的介绍,下一篇是python2中编码问题...

hc321
32分钟前
1
0
基于OpenSSL的一些常用加密签名算法

目前包括:MD5、SHA512、DES、RSA加解密、RSA+MD5签名验证算法,在openssl基础上再进行封装,使用简单,头文件需要包含openssl库,可以使用vcpkg自动管理,省去繁琐的配置工程的过程。 该RSA...

LoSingSang
41分钟前
1
0
spring Data JPA

什么是JPA? 全称Java Persistence API,可以通过注解或者XML描述【对象-关系表】之间的映射关系,并将实体对象持久化到数据库中。 为我们提供了: 1)ORM映射元数据:JPA支持XML和注解两种元...

狼王黄师傅
46分钟前
1
0
微信小程序 - 使用七牛云 API 截取第 n 秒图像为封面图

前面分享过七牛的上传操作,在这里说下使用七牛 api 对视频在页面的处理,比如你的视频上传之后获取七牛视频链接,这时候你怎么展示它呢? 在页面可以使用小程序提供的原生组件 video ,可以...

几个栗子
49分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部