Leetcode：多數(shù)元素

每日一題，讓你身心疲憊！

不要擔(dān)心，后續(xù)的痛苦還有很多！

題目：

給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

leetcode地址：https://leetcode-cn.com/problems/majority-element/

示例 1：

輸入：[3,2,3]
輸出：3

解題思路：

1、哈希

首先就可以想到用哈希去做一個(gè)暴力解法

?public?int?majorityElement(int[]?nums)?{
????int?len?=?nums.length;
????int?moreLen?=?len?/?2?;
????int?result?=?nums[0];
????Map?tmpMap?=?new?HashMap<>();
????for?(int?i?=?0;?i?????????Integer?currNum?=?tmpMap.getOrDefault(nums[i],?0)?+?1;
????????tmpMap.put(nums[i],??currNum);
????????if?(currNum?>?moreLen)?{
????????????return?nums[i];
????????}
????}
????return?result;
}

2、排序

既然是尋找出現(xiàn)次數(shù)大于 n/2 的數(shù)字，那么可以對(duì)數(shù)組先進(jìn)行排序，然后中間的數(shù)字就是正解了。

?public?static?int?majorityElement(int[]?nums)?{
????????Arrays.sort(nums);
????????return?nums[nums.length?/?2];
????}

3、摩爾投票法

將目標(biāo)數(shù)字（target_num）初始化為nums[0]，票數(shù)count初始化為1。

當(dāng)遇到與target_num相同的數(shù)，則票數(shù)count = count + 1，否則票數(shù)count = count - 1。

當(dāng)票數(shù)count為0時(shí)，更換候選人，并將票數(shù)count重置為1。

遍歷完數(shù)組后，target_num即為最終答案。

解釋?zhuān)?/strong>

投票法是遇到相同的則票數(shù) + 1，遇到不同的則票數(shù) - 1。

且“多數(shù)元素”的個(gè)數(shù)> ? n/2 ?，其余元素的個(gè)數(shù)總和<= ? n/2 ?。

因此“多數(shù)元素”的個(gè)數(shù) - 其余元素的個(gè)數(shù)總和 的結(jié)果 肯定 >= 1。

這就相當(dāng)于每個(gè)“多數(shù)元素”和其他元素 兩兩相互抵消，抵消到最后肯定還剩余至少1個(gè)“多數(shù)元素”。

public?int?majorityElement(int[]?nums)?{
????int?cand_num?=?nums[0],?count?=?1;
????for?(int?i?=?1;?i?????????if?(cand_num?==?nums[i])
????????????++count;
????????else?if?(--count?==?0)?{
????????????cand_num?=?nums[i];
????????????count?=?1;
????????}
????}
????return?cand_num;
}

總結(jié)：

從上可以看到，解題效率是：投票法 > 排序法 > 哈希法

算法主要在于思維方式，可能一開(kāi)始我們只能想到的是暴力解法，有問(wèn)題嗎？沒(méi)有問(wèn)題，能解出來(lái)叫牛逼，沒(méi)解出來(lái)叫事故。此時(shí)也不要懊惱，可以看看別人的解法，或許可以讓你茅塞頓開(kāi)，后續(xù)多加練習(xí)，遇到相同題型自然就會(huì)有思路了。

最后：周末愉快！