# Question

Formatted question description: https://leetcode.ca/all/169.html

 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 the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

@tag-array



# Algorithm

First of all, there is a prerequisite, there must be a number that appears more than half of the number, then if the counter is reduced to 0, it means that the number of numbers that are not candidates currently is the same as the number of candidates, then this candidate It is already very weak, and it may not appear more than half. At this time, choose to replace the current candidate.

Or, after sorting, mid is always the majority.

Java