文档章节

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

I
 Iter_迟cH1
发布于 2016/08/10 15:32
字数 160
阅读 21
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
0
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
0
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
0
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
2
0
openJDK之sun.misc.Unsafe类CAS底层实现

注:这篇文章参考了https://www.cnblogs.com/snowater/p/8303698.html 1.sun.misc.Unsafe中CAS方法 在sun.misc.Unsafe中CAS方法如下: compareAndSwapObject(java.lang.Object arg0, long a......

汉斯-冯-拉特
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部