Leetcode 07 java

169. 多數元素

給定一個大小為?n?的數組?nums?，返回其中的多數元素。

多數元素是指在數組中出現次數?大于?? n/2 ??的元素。

你可以假設數組是非空的，并且給定的數組總是存在多數元素。

示例?1：

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

示例?2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示：

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

進階：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的算法解決此問題。

我的想法：

之前一眼hash的時候用的是異或，這個題目不是簡單的計數，所以大概hash也是可行的吧，嗯...異或只能判斷出現的奇偶性。

1 分析一下異或，hash的解法可行性

你的想法嘗試使用哈希或異或操作來解決問題，不過這兩種方法在這個問題上有一些限制：

1.?異或操作的局限性

你提到 "異或只能判斷出現的奇偶性"，這是正確的。異或（XOR）的性質是：

相同元素異或結果為 0（如?a ^ a = 0）
任何元素與 0 異或結果為自身（如?a ^ 0 = a）

因此，如果一個元素出現奇數次，異或結果會保留該元素；但如果出現偶數次，異或結果會抵消為 0。然而，這個問題要求的是 " 出現次數大于 n/2" 的元素，而異或無法直接統計次數或比較頻率，所以異或在這里不適用。

2.?哈希表的正確用法

雖然你提到 "hash 也是可行的吧"，但需要注意哈希表的具體用法：

錯誤用法：若用哈希表存儲元素的異或結果，無法解決問題（與直接異或數組相同）。
正確用法：用哈希表統計每個元素的出現次數，然后遍歷哈希表找到次數超過 n/2 的元素。

例如：

java

運行

import java.util.HashMap;
import java.util.Map;class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> countMap = new HashMap<>();for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);}for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {if (entry.getValue() > nums.length / 2) {return entry.getKey();}}return -1; // 題目保證存在多數元素，不會執行到這里}
}

這個方法的時間和空間復雜度都是 O (n)，符合題目要求，但不是最優解。

3.?最優解法：摩爾投票法（Boyer-Moore Voting Algorithm）

如果追求 O (1) 空間復雜度，可以使用摩爾投票法：

java

運行

class Solution {public int majorityElement(int[] nums) {int count = 0;Integer candidate = null;for (int num : nums) {if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;}return candidate;}
}

原理：

遍歷數組時維護一個候選元素?candidate?和計數器?count。
遇到與?candidate?相同的元素，count +1；否則?count -1。
當?count?減為 0 時，更換候選元素為當前元素。
由于多數元素出現次數超過一半，最終候選元素一定是多數元素。

總結

你的方向（哈希或異或）有一定合理性，但需要注意：

異或無法直接解決該問題，因為它不統計次數，只判斷奇偶性。
哈希表需要用于統計次數，而不是異或操作。
摩爾投票法是最優解，滿足 O (n) 時間和 O (1) 空間。

2 hash表解法

import java.util.HashMap;
import java.util.Map;class Solution {public int majorityElement(int[] nums) {// 1. 創建一個哈希表，鍵為數組中的元素，值為該元素出現的次數Map<Integer, Integer> countMap = new HashMap<>();// 2. 遍歷數組中的每個元素for (int num : nums) {// 3. 對于當前元素num，獲取它在哈希表中已有的計數//    getOrDefault方法：如果num存在，返回其計數；否則返回默認值0int currentCount = countMap.getOrDefault(num, 0);// 4. 將當前元素的計數加1，并更新到哈希表中//    put方法：將鍵值對 (num, currentCount + 1) 存入哈希表//    如果鍵num已存在，會覆蓋舊值；如果不存在，則創建新的鍵值對countMap.put(num, currentCount + 1);}// 5. 遍歷哈希表，找出出現次數超過數組長度一半的元素for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {// entry.getKey() 返回當前鍵（元素值）// entry.getValue() 返回當前值（出現次數）if (entry.getValue() > nums.length / 2) {return entry.getKey();}}// 根據題目假設，數組中總是存在多數元素，因此不會執行到這里return -1;}
}

關于`put`方法的詳細解釋

put是 HashMap 類的核心方法，用于存儲或更新鍵值對：

java

運行

map.put(key, value);

功能：
- 如果key不存在于哈希表中：創建新的鍵值對(key, value)。
- 如果key已存在：用新的value覆蓋舊值（舊值會被丟棄）。

示例：

java

運行

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90);    // 添加新鍵值對：Alice -> 90
scores.put("Bob", 85);      // 添加新鍵值對：Bob -> 85
scores.put("Alice", 95);    // 更新已有鍵：Alice -> 95（舊值90被覆蓋）

在本題中的作用：

java

運行
```
countMap.put(num, currentCount + 1);
```
?
這行代碼會將元素num的計數更新為currentCount + 1，無論num之前是否存在于哈希表中。

復雜度分析

時間復雜度：O (n) —— 遍歷數組一次，遍歷哈希表一次。
空間復雜度：O (n) —— 最壞情況下，哈希表需要存儲所有元素。

getOrDefault?是 Java 中?Map?接口提供的一個實用方法，用于安全地獲取鍵對應的值，避免?NullPointerException。我來詳細解釋它的用法和在這個問題中的作用。

`getOrDefault`?方法詳解

方法簽名

java

運行

V getOrDefault(Object key, V defaultValue);

參數：
- key：要查找的鍵。
- defaultValue：如果鍵不存在時返回的默認值。
返回值：
- 如果鍵存在，返回對應的值；
- 如果鍵不存在，返回?defaultValue。

為什么需要?`getOrDefault`？

在統計元素次數時，傳統寫法需要先檢查鍵是否存在，不存在則初始化為 0，存在則加 1：

java

運行

// 傳統寫法（不使用 getOrDefault）
if (countMap.containsKey(num)) {// 鍵存在，取出舊值并加 1int oldCount = countMap.get(num);countMap.put(num, oldCount + 1);
} else {// 鍵不存在，初始化為 1countMap.put(num, 1);
}

使用?getOrDefault?可以簡化這個邏輯，一行代碼完成統計：

java

運行

// 等效寫法（使用 getOrDefault）
int currentCount = countMap.getOrDefault(num, 0); // 不存在則默認 0
countMap.put(num, currentCount + 1); // 直接更新計數

在多數元素問題中的應用

讓我結合原題代碼，逐行解釋?getOrDefault?的作用：

java

運行

import java.util.HashMap;
import java.util.Map;class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> countMap = new HashMap<>();for (int num : nums) {// 1. 獲取當前元素 num 的已有計數//    如果 num 第一次出現，getOrDefault 返回默認值 0//    如果 num 已存在，返回其當前計數int currentCount = countMap.getOrDefault(num, 0);// 2. 將計數加 1 后存入哈希表//    如果 num 是第一次出現，這行代碼會創建新的鍵值對 (num, 1)//    如果 num 已存在，這行代碼會覆蓋舊值，更新為新的計數countMap.put(num, currentCount + 1);}// ...后續代碼不變...}
}

對比實驗：理解?`getOrDefault`?的行為

假設我們有一個空的哈希表?countMap，執行以下操作：

java

運行

Map<Integer, Integer> countMap = new HashMap<>();// 第一次遇到元素 3
int count1 = countMap.getOrDefault(3, 0); // 返回 0（鍵不存在）
countMap.put(3, count1 + 1); // 存入 (3, 1)// 第二次遇到元素 3
int count2 = countMap.getOrDefault(3, 0); // 返回 1（鍵已存在）
countMap.put(3, count2 + 1); // 存入 (3, 2)// 最終哈希表中：{3=2}

其他常見用法場景

統計字符串中字符出現次數：

java

運行

String s = "hello";
Map<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) {charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// 結果：{h=1, e=1, l=2, o=1}

分組統計：

java

運行

List<String> words = Arrays.asList("apple", "banana", "apple");
Map<Integer, Integer> lengthCount = new HashMap<>();
for (String word : words) {int length = word.length();lengthCount.put(length, lengthCount.getOrDefault(length, 0) + 1);
}
// 結果：{5=1, 6=2}（長度為5的單詞1個，長度為6的單詞2個）

總結

getOrDefault?是處理哈希表計數問題的 “語法糖”，它的核心優勢是：

簡化代碼：避免了手動檢查鍵是否存在的繁瑣邏輯。
防止空指針異常：當鍵不存在時返回默認值（如 0），而不是?null。
代碼可讀性：讓統計邏輯更加清晰直觀。

在處理需要初始化默認值的場景時，它是 Java 程序員的常用工具之一！

3?摩爾投票法（Boyer-Moore Voting Algorithm）

摩爾投票法（Boyer-Moore Voting Algorithm），這個算法的核心思想可以用一句話概括："多數元素在數組中出現的次數超過一半，因此即使與其他所有元素兩兩抵消，最終也會剩下至少一個自身"。

class Solution {public int majorityElement(int[] nums) {// 初始化計數器，用于記錄當前候選人的票數int count = 0;// 初始化候選人，Integer類型允許為null，表示尚未選出候選人Integer candidate = null;// 遍歷數組中的每個元素for (int num : nums) {// 當計數器為0時，意味著當前候選人的票數已被完全抵消// 需要選擇當前元素作為新的候選人if (count == 0) {candidate = num;}// 根據當前元素是否等于候選人來更新計數器：// - 如果相等，說明遇到了支持者，票數+1// - 如果不等，說明遇到了反對者，票數-1count += (num == candidate) ? 1 : -1;}// 遍歷結束后，最終的候選人即為多數元素// 由于多數元素的數量超過n/2，即使中途被抵消，最終也會勝出return candidate;}
}

核心邏輯解釋

候選人交替：
- 當count減為 0 時，說明當前候選人的支持票被反對票完全抵消，此時需要更換候選人為當前元素。
票數更新：
- 遇到與候選人相同的元素時，count增加 1（支持票）
- 遇到與候選人不同的元素時，count減少 1（反對票）
最終勝利條件：
- 由于多數元素的出現次數超過一半，即使在遍歷過程中被其他元素抵消，最終也會因為自身數量優勢重新成為候選人并保持到最后。

算法核心思想

想象一場投票選舉，每個候選人需要和對手 "一對一拼消耗"：

每次遇到自己的支持者，票數?+1；
每次遇到對手，票數?-1；
當票數減為?0?時，當前候選人 "下臺"，由新的候選人接替。

由于多數元素的支持者超過半數，即使其他所有候選人聯合起來抵消票數，多數元素最終仍會勝出。

算法步驟拆解

我們用數組?[2, 2, 1, 1, 1, 2, 2]?為例，逐步演示算法過程：

初始化：
- candidate（當前候選人）：null
- count（當前票數）：0
遍歷數組：
- 第 1 個元素?2：
  - 當前?count = 0，任命?2?為新候選人，count +1?→?1。
  - 狀態：candidate = 2,?count = 1。
- 第 2 個元素?2：
  - 與候選人相同，count +1?→?2。
  - 狀態：candidate = 2,?count = 2。
- 第 3 個元素?1：
  - 與候選人不同，count -1?→?1。
  - 狀態：candidate = 2,?count = 1。
- 第 4 個元素?1：
  - 與候選人不同，count -1?→?0。
  - 狀態：candidate = 2,?count = 0（候選人下臺）。
- 第 5 個元素?1：
  - 當前?count = 0，任命?1?為新候選人，count +1?→?1。
  - 狀態：candidate = 1,?count = 1。
- 第 6 個元素?2：
  - 與候選人不同，count -1?→?0。
  - 狀態：candidate = 1,?count = 0（候選人下臺）。
- 第 7 個元素?2：
  - 當前?count = 0，任命?2?為新候選人，count +1?→?1。
  - 狀態：candidate = 2,?count = 1。
遍歷結束：最終候選人是?2，返回?2。

代碼實現（Java）

java

運行

class Solution {public int majorityElement(int[] nums) {int count = 0;        // 記錄當前候選人的票數Integer candidate = null;  // 當前候選人（初始為 null）for (int num : nums) {// 當票數為 0 時，更換候選人if (count == 0) {candidate = num;}// 根據當前元素是否等于候選人，更新票數count += (num == candidate) ? 1 : -1;}return candidate;  // 最終剩下的候選人即為多數元素}
}

關鍵細節解釋

為什么?count = 0?時更換候選人？
- 當?count = 0?時，說明當前候選人的票數已被完全抵消，需要重新選擇候選人。
- 由于多數元素的數量超過一半，即使中途被其他元素抵消，最終仍會重新成為候選人并勝出。
為什么不需要驗證最終候選人？
- 根據算法邏輯，多數元素的數量超過?n/2，因此無論其他元素如何抵消，多數元素最終的票數至少為?1。
- 因此，最后剩下的候選人必然是多數元素。

復雜度分析

時間復雜度：O (n) —— 只需遍歷一次數組。
空間復雜度：O (1) —— 只需要常數級的額外空間。

進階思考：如果沒有多數元素會怎樣？

如果數組中不存在多數元素，摩爾投票法會返回一個錯誤的結果。例如：

數組?[1, 2, 3]：最終返回?3，但?3?并不是多數元素。

因此，如果題目沒有明確保證存在多數元素，需要在算法結束后額外驗證最終候選人是否真的超過半數：

java

運行

// 增加驗證步驟
int candidate = majorityElement(nums);  // 調用摩爾投票法
int count = 0;
for (int num : nums) {if (num == candidate) count++;
}
if (count > nums.length / 2) {return candidate;
} else {return -1;  // 不存在多數元素
}