169. Majority Element (solution 1)

package LeetCode_169

/**
 * 169. Majority Element
 * https://leetcode.com/problems/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
 * */
class Solution {
    /*
    * solution 1: HashMap, Time:O(n), Space:O(n)
    * solution 2: Moore Vote, Time:O(n), Space:O(1)
    * */
    fun majorityElement(nums: IntArray): Int {
        val size = nums.size
        val map = HashMap<Int, Int>()
        for (item in nums) {
            map.put(item, map.getOrDefault(item, 0) + 1)
        }
        var result = -1
        for (item in map) {
            if (item.value > (size / 2)) {
                result = item.key
                break
            }
        }
        return result
    }
}