20: Majority item

Given an array of integers. Find an item that appears more than ⌊n/2⌋ times

Note: Majority item always exists

 

Example 1

Input: [1, 1, 3]

Output: 1

Example 2

Input: [1, 1, 3, 3 ,4, 3]

Output: 3