主題
題目連結(jié)：
題目意譯：
一個(gè)長(zhǎng)度為 m 的整數(shù)陣列 arr 中的一個(gè)元素 x 如果滿足 freq(x) × 2 > m，其中 freq(x) 為 arr 中 x 的出現(xiàn)次數(shù)，則該元素為「主要的」。注意到這個(gè)定義隱含著 arr 最多只有一個(gè)主要元素。
你被給定一個(gè)索引值從 0 開(kāi)始數(shù)、長(zhǎng)度為 n 且有著一個(gè)主要元素的整數(shù)陣列 nums。
你可以將 nums 從索引值 i 分切成兩個(gè)診列 nums[0, ……, i] 以及 nums[i + 1, ……, n - 1]，而該分切方式是合法的若且唯若：
0 ≦ i < n - 1
nums[0, ……, i] 和 nums[i + 1, ……, n - 1] 有著相同的主要元素。
其中 nums[i, ……, j] 代表著 nums 的一個(gè)子陣列，其從索引值 i 開(kāi)始（含）並結(jié)束於索引值 j（含）。此外，如果 j < i，則 nums[i, ……, j] 代表著一個(gè)空的子陣列。
回傳一個(gè)合法分切的最小索引值。如果合法分切的方式不存在，則回傳 -1。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
nums 有恰好一個(gè)主要元素。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [1,2,2,2]
輸出： 2
解釋?zhuān)何覀兛梢栽谒饕?2 將 nums 分切並得到 [1,2,2] 和 [2]。
在陣列 [1,2,2] 中，元素 2 是主要元素因?yàn)槠湓陉嚵谐霈F(xiàn)了兩次，並且 2 × 2 > 3。
在陣列 [2] 中，元素 2 是主要元素因?yàn)槠湓陉嚵谐霈F(xiàn)了一次，並且 1 × 2 > 1。
[1,2,2] 和 [2] 都與 nums 有著相同的主要元素，所以此為一個(gè)合法分切。
可以證明索引值 2 是所有合法分切方式中最小者。
範(fàn)例 2：
輸入： nums = [2,1,3,1,1,1,7,1,2,1]
輸出： 4
解釋?zhuān)何覀兛梢栽谒饕?4 將 nums 分切並得到 [2,1,3,1,1] 和 [1,7,1,2,1]。
在陣列 [2,1,3,1,1] 中，元素 1 是主要元素因?yàn)槠湓陉嚵谐霈F(xiàn)了三次，並且 3 × 2 > 5。
在陣列 [1,7,1,2,1] 中，元素 1 是主要元素因?yàn)槠湓陉嚵谐霈F(xiàn)了三次，並且 3 × 2 > 5。
[2,1,3,1,1] 和 [1,7,1,2,1] 都與 nums 有著相同的主要元素，所以此為一個(gè)合法分切。
可以證明索引值 4 是所有合法分切方式中最小者。
範(fàn)例 3：
輸入： nums = [3,3,3,3,7,2,2]
輸出： -1
解釋?zhuān)?可以證明合法分切不存在。
解題思維：
首先，以前有提過(guò)博耶—摩爾多數(shù)投票演算法（Boyer–Moore majority vote algorithm），參見(jiàn)這題。可以先用來(lái)找 nums 中的主要元素是哪一個(gè)。
找到主要元素是哪一個(gè)之後（設(shè)其值為 X），再掃過(guò) nums 一次來(lái)統(tǒng)計(jì)實(shí)際上出現(xiàn)多少次（假設(shè)為 C 次）。
而回到題目的分切：
「左半」和「右半」各自的主要元素要都是 X。而這代表著如果左半中有 C' 個(gè) X 出現(xiàn)在其中，另一邊會(huì)是 C - C' 並且兩數(shù)滿足 2C' > 左半長(zhǎng)度、2(C - C') > 右半長(zhǎng)度。
因此我們可以由小到大窮舉索引值 i 來(lái)得到「左半」（可以看到 i = k + 1 時(shí)的 C' 值至少跟 i = k 時(shí)的 C' 一樣大，所以可以「繼承」），而一旦遇到 X 就將計(jì)數(shù)用的變數(shù) + 1。而該變數(shù)便是索引值 i 的分切之左半的 C' 之值。然後根據(jù)上面的條件判斷合不合法即可找到最小的合法分切索引值。如果找不到，則回傳 -1。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
