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.

提示	解題應用
HashTable	HashMap

Default:

func majorityElement(nums []int) int {

}

解答思路:

雖然本題的標籤提示為Array，不過我自己覺得用HashTable的方式處理比較直覺，即然要計算每個數字出現的頻率，Map方式做儲存或許是最簡單的方式，所以藉由Map來統計每個數字出現了多少次，每次當該數字出現時，先從Map拿出該數字出現的次數並+1，接著判斷出現的次數有沒有超過全體數字的一半，有的話就直接回傳該數字不需要繼續做統計，沒有則將該數字出現的次數+1放回Map之中繼續做統計。

程式碼解說:

一開始先初始化我們要的Map類型，我把出現的該數字當做key值，value當然就是出現的次數，接著當然就是用for一個個取出數字開始做統計，首先先從Map取出該數字出現的次數，接著+1並判斷是否超過全部數字的一半，有的話就回傳該數字，不過如果Map目前根本就沒有存入那個數字的話呢?沒有的話再放入即可，因為此時取出的值為0，一樣+1再把該數字與出現次數放入Map，並不需要特別再多一步判斷是否存在，而題目有明說必定存在一個高頻率的數字，不過對於不存在的狀況還是要回傳一個值，所以就用0來替代一下

element := make(map[int]int)
for _, v := range nums {
	times, _ := element[v]
	if times+1 > len(nums)/2 {
		return v
	}
	element[v] = times + 1
}
return 0

完整程式碼:

func majorityElement(nums []int) int {
	element := make(map[int]int)
	for _, v := range nums {
		times, _ := element[v]
		if times+1 > len(nums)/2 {
			return v
		}
		element[v] = times + 1
	}
	return 0
}

總結:

統計一陣列數字出現的頻率，採用HashMap的方式做儲存或許最直覺且簡單。