LeetCode如何求數組中的絕對眾數

LeetCode如何求數組中的絕對眾數

在算法和數據結構的學習中，求解數組中的絕對眾數是一個經典且常見的問題。絕對眾數是指在數組中出現次數超過數組長度一半的元素。本文將詳細介紹如何在LeetCode上解決這個問題，包括不同的解題思路、代碼實現以及復雜度分析。

1. 問題描述

給定一個大小為 n 的數組 nums，找到其中的絕對眾數。絕對眾數是指在數組中出現次數超過 n/2 的元素。假設數組非空，并且絕對眾數一定存在。

示例 1:

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

示例 2:

輸入: [2, 2, 1, 1, 1, 2, 2]
輸出: 2

2. 解題思路

2.1 暴力解法

最直觀的解法是遍歷數組中的每一個元素，統計每個元素出現的次數，如果某個元素的出現次數超過 n/2，則返回該元素。

時間復雜度: O(n^2)

空間復雜度: O(1)

代碼實現:

def majorityElement(nums):
    n = len(nums)
    for num in nums:
        count = 0
        for elem in nums:
            if elem == num:
                count += 1
        if count > n // 2:
            return num
    return -1

2.2 哈希表法

為了優化時間復雜度，可以使用哈希表來記錄每個元素的出現次數。遍歷數組時，將元素作為鍵，出現次數作為值存儲在哈希表中。最后遍歷哈希表，找到出現次數超過 n/2 的元素。

時間復雜度: O(n)

空間復雜度: O(n)

代碼實現:

def majorityElement(nums):
    counts = {}
    n = len(nums)
    for num in nums:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1
        if counts[num] > n // 2:
            return num
    return -1

2.3 排序法

將數組排序后，絕對眾數一定會出現在數組的中間位置。因此，排序后直接返回中間位置的元素即可。

時間復雜度: O(n log n)

空間復雜度: O(1) 或 O(n)（取決于排序算法的實現）

代碼實現:

def majorityElement(nums):
    nums.sort()
    return nums[len(nums) // 2]

2.4 摩爾投票法

摩爾投票法（Boyer-Moore Voting Algorithm）是一種高效的算法，用于在O(n)時間復雜度和O(1)空間復雜度內找到絕對眾數。該算法的核心思想是通過消除不同的元素來找到候選的絕對眾數。

算法步驟:

1. 初始化候選元素 candidate 和計數器 count。
2. 遍歷數組中的每一個元素：
   • 如果 count 為0，則將當前元素設為候選元素 candidate。
   • 如果當前元素等于 candidate，則 count 加1；否則 count 減1。
3. 最后，candidate 即為絕對眾數。

時間復雜度: O(n)

空間復雜度: O(1)

代碼實現:

def majorityElement(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

3. 復雜度分析

3.1 暴力解法

• 時間復雜度: O(n^2)
  • 需要兩層循環，外層循環遍歷每個元素，內層循環統計每個元素的出現次數。
• 空間復雜度: O(1)
  • 只使用了常數級別的額外空間。

3.2 哈希表法

• 時間復雜度: O(n)
  • 只需要遍歷數組一次，統計每個元素的出現次數。
• 空間復雜度: O(n)
  • 需要使用哈希表來存儲每個元素的出現次數。

3.3 排序法

• 時間復雜度: O(n log n)
  • 排序的時間復雜度為O(n log n)。
• 空間復雜度: O(1) 或 O(n)
  • 取決于排序算法的實現，原地排序的空間復雜度為O(1)，非原地排序的空間復雜度為O(n)。

3.4 摩爾投票法

• 時間復雜度: O(n)
  • 只需要遍歷數組一次。
• 空間復雜度: O(1)
  • 只使用了常數級別的額外空間。

4. 實際應用

在實際應用中，摩爾投票法是最優的解決方案，因為它不僅時間復雜度低，而且空間復雜度也非常低。特別是在處理大規模數據時，摩爾投票法能夠顯著提高算法的效率。

5. 總結

本文詳細介紹了如何在LeetCode上求解數組中的絕對眾數問題，包括暴力解法、哈希表法、排序法和摩爾投票法。通過對不同方法的復雜度分析，我們可以看出摩爾投票法在時間和空間復雜度上都具有顯著優勢。因此，在實際應用中，推薦使用摩爾投票法來解決類似的問題。

6. 參考代碼

以下是四種方法的完整代碼實現：

# 暴力解法
def majorityElement1(nums):
    n = len(nums)
    for num in nums:
        count = 0
        for elem in nums:
            if elem == num:
                count += 1
        if count > n // 2:
            return num
    return -1

# 哈希表法
def majorityElement2(nums):
    counts = {}
    n = len(nums)
    for num in nums:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1
        if counts[num] > n // 2:
            return num
    return -1

# 排序法
def majorityElement3(nums):
    nums.sort()
    return nums[len(nums) // 2]

# 摩爾投票法
def majorityElement4(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

# 測試用例
nums1 = [3, 2, 3]
nums2 = [2, 2, 1, 1, 1, 2, 2]

print(majorityElement1(nums1))  # 輸出: 3
print(majorityElement2(nums1))  # 輸出: 3
print(majorityElement3(nums1))  # 輸出: 3
print(majorityElement4(nums1))  # 輸出: 3

print(majorityElement1(nums2))  # 輸出: 2
print(majorityElement2(nums2))  # 輸出: 2
print(majorityElement3(nums2))  # 輸出: 2
print(majorityElement4(nums2))  # 輸出: 2

通過以上代碼，我們可以驗證不同方法的正確性和效率。在實際應用中，選擇合適的方法可以顯著提高算法的性能。