題?描述

數(shù)組中有?個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組?度的?半，請找出這個數(shù)字。例如輸??個?度為 9 的數(shù)組 {1,2,3,2,2,2,5,4,2} 。由于數(shù)字 2 在數(shù)組中出現(xiàn)了 5 次，超過數(shù)組?度的?半，因此輸出 2 。如果不存在則輸出 0 。

思路及解答

哈希表法（HashMap）

哈希表法通過統(tǒng)計每個數(shù)字的出現(xiàn)次數(shù)來解決問題。遍歷數(shù)組時，使用哈希表記錄每個數(shù)字出現(xiàn)的次數(shù)，一旦發(fā)現(xiàn)某個數(shù)字的出現(xiàn)次數(shù)超過數(shù)組長度的一半，立即返回該數(shù)字。

public class Solution {
    public int MoreThanHalfNum(int[] nums) {
        // 創(chuàng)建哈希表，key為數(shù)字，value為出現(xiàn)次數(shù)
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 獲取當(dāng)前數(shù)字的出現(xiàn)次數(shù)并加1，若不存在則初始化為0再加1
            int count = map.getOrDefault(num, 0) + 1;
            // 若當(dāng)前數(shù)字出現(xiàn)次數(shù)已超過數(shù)組長度一半，則返回該數(shù)字
            if (count > nums.length / 2) {
                return num;
            }
            map.put(num, count); // 更新哈希表
        }
        return 0; // 如果不存在多數(shù)元素，返回0（但題目假設(shè)總是存在）
    }
}

• 時間復(fù)雜度?：O(n)，其中 n 是數(shù)組的長度。我們只需遍歷數(shù)組一次。
• ?空間復(fù)雜度?：O(n)，最壞情況下需要存儲所有不同的數(shù)字。

排序法

排序法的思路非常巧妙：?由于多數(shù)元素的數(shù)量超過數(shù)組長度的一半，那么將數(shù)組排序后，中間位置的元素一定是多數(shù)元素。

public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums); // 對數(shù)組進(jìn)行排序
        return nums[nums.length / 2]; // 返回中間位置的元素
    }
}

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

1. 如果使? hashmap 直接統(tǒng)計，需要額外的空間，我們不希望使?額外空間;
2. 如果使?排序之后再統(tǒng)計，需要時間復(fù)雜度為O(nlogn)， 我們希望時間復(fù)雜度更低?點。

摩爾投票法是一種高效且空間復(fù)雜度低的算法。其核心思想是通過票數(shù)的抵消來找出多數(shù)元素。算法維護(hù)一個候選眾數(shù) candidate 和其票數(shù) count。遍歷數(shù)組時，若 count 為0，則選擇當(dāng)前數(shù)字作為候選；若當(dāng)前數(shù)字與候選相同，則票數(shù)加1，否則減1。由于多數(shù)元素的存在，最終剩下的候選一定是多數(shù)元素。

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0; // 候選眾數(shù)
        int count = 0;     // 票數(shù)統(tǒng)計
        
        for (int num : nums) {
            if (count == 0) { // 如果票數(shù)為0，選擇當(dāng)前數(shù)字作為候選
                candidate = num;
            }
            // 如果當(dāng)前數(shù)字與候選相同，則票數(shù)加1，否則減1
            count += (num == candidate) ? 1 : -1;
        }
        
        // 可選：驗證candidate是否真的是多數(shù)元素（根據(jù)題目假設(shè)，通常不需要）
        // 但如果題目要求不存在多數(shù)元素時返回0，則需要驗證步驟
        count = 0;
        for (int num : nums) {
            if (num == candidate) count++;
        }
        
        return count > nums.length / 2 ? candidate : 0;
    }
}

• 時間復(fù)雜度?：O(n)，只需遍歷數(shù)組兩次（一次投票，一次驗證）。
• ?空間復(fù)雜度?：O(1)，只使用了常數(shù)個額外變量