文档章节

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

I
 Iter_迟cH1
发布于 2016/08/10 15:32
字数 160
阅读 31
收藏 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
LeetCode算法题-Majority Element(Java实现)

这是悦乐书的第181次更新,第183篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第40题(顺位题号是169)。给定大小为n的数组,找到数组中出现次数超过n/2的元素。假设该数组非...

小川94
11/24
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
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

没有更多内容

加载失败,请刷新页面

加载更多

Andrew Ng教你如何引领公司进入AI时代

摘要: 人工智能时代,企业转型遇到困难?看看Andrew Ng的建议吧! AI(人工智能)技术就像100年前的电力一样,正准备改变每个行业。从现在到2030年,它将创造约13万亿美元的GDP增长。虽然它...

阿里云官方博客
7分钟前
0
0
斗图咖(www.doutuka.com)上线纪念

网站名称:斗图咖 网站描述:是一款年轻人都在玩的斗图网站,来斗图咖一起斗图装逼交朋友吧。站长每天上传收集的最新最火斗图,供大家娱乐聊天发表情;后期也会开发表情自主设计,自己设计表...

focusone
28分钟前
3
0
Spring AOP 切面编程记录日志和接口执行时间

最近客户现在提出系统访问非常慢,需要优化提升访问速度,在排查了nginx、tomcat内存和服务器负载之后,判断是数据库查询速度慢,进一步排查发现是因为部分视图和表查询特别慢导致了整个系统...

编程SHA
39分钟前
5
0
15个Spring的核心注释示例

众所周知,Spring DI和Spring IOC是Spring Framework的核心概念。让我们从org.springframework.beans.factory.annotation和org.springframework.context.annotation包中探索一些Spring核心注......

java菜分享
45分钟前
2
0
[LintCode] Binary Tree Level Order Traversal(二叉树的层次遍历)

描述 给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 样例 给一棵二叉树 {3,9,20,#,#,15,7} : 3 / \9 20 / \ 15 7 返回他的分层遍历结果: [ [3], [...

honeymose
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部