find-majority-element-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

A majority element is an element that makes up more than half of the items in an array. Given a&nbsp;integers array, find the majority element. If there is no majority element, return -1. Do this in O(N) time and O(1) space.

Example 1: 

<pre>
Input: [1,2,5,9,5,9,5,5,5]
Output: 5</pre>

&nbsp;

Example 2: 

<pre>
Input: [3,2]
Output: -1</pre>

&nbsp;

Example 3: 

<pre>
Input: [2,2,1,1,1,2,2]
Output: 2
</pre>

majorityElement

Find Majority Element LCCI

Array

Counting

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 <code>-1</code> 。请设计时间复杂度为 <code>O(N)</code> 、空间复杂度为 <code>O(1)</code> 的解决方案。

 

示例 1：

<pre>
输入：[1,2,5,9,5,9,5,5,5]
输出：5</pre>

示例 2：

<pre>
输入：[3,2]
输出：-1</pre>

示例 3：

<pre>
输入：[2,2,1,1,1,2,2]
输出：2</pre>