問題背景
在資料分析和系統監控中，頻率統計是一個基礎且重要的操作。特別是在資源受限的嵌入式系統或高併發場景下，如何高效地統計給定範圍內數字的出現頻率，直接影響系統的效能表現。
OAVOService 面試助攻團隊 在長期的大廠演算法面試輔導中發現，頻率統計問題經常出現在 Google、Amazon、Microsoft 等公司的程式設計面試中，是考察候選人對時空權衡、陣列操作技巧的經典題目。
問題描述
Problem 3 — Print Frequency of Numbers from 1 to N
給定一個包含 N 個整數的陣列，陣列中只包含 1 到 N 的整數。某些數字可能出現多次，某些數字可能不出現。
編寫程式碼印出 1 到 N 每個數字在陣列中出現的次數。
範例：
PrintFrequency(new int[] {3, 1, 2});
輸出:
1 : 1
2 : 1
3 : 1
PrintFrequency(new int[] {2, 4, 4, 6, 6, 6});
輸出:
1 : 0
2 : 1
3 : 0
4 : 2
5 : 0
6 : 3
核心考察點：
- 陣列遍歷與計數演算法
- 空間複雜度優化技巧
- 原地操作的陣列修改策略
- 邊界條件處理
解法分析
解法一：標準計數陣列（推薦）
def print_frequency_standard(arr):
"""
標準計數陣列解法
時間複雜度: O(n)
空間複雜度: O(n)
"""
if not arr:
return
n = len(arr)
# 建立計數陣列，索引0對應數字1
count = [0] * n
# 統計每個數字的頻率
for num in arr:
if 1 <= num <= n: # 邊界檢查
count[num - 1] += 1
# 印出結果
for i in range(n):
print(f"{i + 1} : {count[i]}")
# 優化版本：支援任意範圍
def print_frequency_range(arr, min_val, max_val):
"""
支援任意數字範圍的頻率統計
"""
count = [0] * (max_val - min_val + 1)
for num in arr:
if min_val <= num <= max_val:
count[num - min_val] += 1
for i in range(len(count)):
print(f"{i + min_val} : {count[i]}")
解法二：原地標記法（進階優化）
def print_frequency_inplace(arr):
"""
原地標記法 - O(1) 額外空間
時間複雜度: O(n)
空間複雜度: O(1)
核心思想：使用陣列元素的正負號來標記存取狀態
"""
if not arr:
return
n = len(arr)
# 第一步：標記出現的數字
for i in range(n):
# 取得目前數字（可能已被標記為負數）
num = abs(arr[i])
if 1 <= num <= n:
# 將對應位置標記為負數（表示該數字出現過）
if arr[num - 1] > 0:
arr[num - 1] = -arr[num - 1]
# 第二步：統計頻率
# 重新遍歷，計算每個數字的出現次數
frequency = [0] * n
for num in arr:
abs_num = abs(num)
if 1 <= abs_num <= n:
frequency[abs_num - 1] += 1
# 第三步：恢復原陣列（可選）
for i in range(n):
arr[i] = abs(arr[i])
# 印出結果
for i in range(n):
print(f"{i + 1} : {frequency[i]}")
解法三：雜湊表法（通用）
from collections import defaultdict, Counter
def print_frequency_hash(arr):
"""
雜湊表解法 - 適用於任意數字範圍
時間複雜度: O(n)
空間複雜度: O(k)，k為不同數字的個數
"""
if not arr:
return
# 方法1：使用Counter
frequency = Counter(arr)
n = len(arr)
for i in range(1, n + 1):
print(f"{i} : {frequency.get(i, 0)}")
# 方法2：手動計數
# count_map = defaultdict(int)
# for num in arr:
# count_map[num] += 1
# for i in range(1, n + 1):
# print(f"{i} : {count_map[i]}")
進階優化策略
1. 分塊處理大陣列
def print_frequency_chunked(arr, chunk_size=1000):
"""
分塊處理大陣列，減少記憶體峰值
適用於記憶體受限場景
"""
if not arr:
return
n = len(arr)
total_count = [0] * n
# 分塊處理
for start in range(0, len(arr), chunk_size):
end = min(start + chunk_size, len(arr))
chunk = arr[start:end]
# 處理目前區塊
chunk_count = [0] * n
for num in chunk:
if 1 <= num <= n:
chunk_count[num - 1] += 1
# 累加到總計數
for i in range(n):
total_count[i] += chunk_count[i]
# 印出結果
for i in range(n):
print(f"{i + 1} : {total_count[i]}")
2. 並行處理優化
from concurrent.futures import ThreadPoolExecutor
import threading
def print_frequency_parallel(arr, num_threads=4):
"""
多執行緒並行處理
適用於大陣列的頻率統計
"""
if not arr:
return
n = len(arr)
chunk_size = len(arr) // num_threads
results = [None] * num_threads
lock = threading.Lock()
def process_chunk(thread_id, start_idx, end_idx):
chunk_count = [0] * n
for i in range(start_idx, end_idx):
num = arr[i]
if 1 <= num <= n:
chunk_count[num - 1] += 1
with lock:
results[thread_id] = chunk_count
# 啟動執行緒
with ThreadPoolExecutor(max_workers=num_threads) as executor:
futures = []
for i in range(num_threads):
start = i * chunk_size
end = len(arr) if i == num_threads - 1 else (i + 1) * chunk_size
future = executor.submit(process_chunk, i, start, end)
futures.append(future)
# 等待所有執行緒完成
for future in futures:
future.result()
# 合併結果
total_count = [0] * n
for chunk_result in results:
if chunk_result:
for i in range(n):
total_count[i] += chunk_result[i]
# 印出結果
for i in range(n):
print(f"{i + 1} : {total_count[i]}")
3. 串流處理大檔案
def print_frequency_streaming(file_path):
"""
串流處理大檔案中的數字頻率
適用於無法一次性載入到記憶體的大資料集
"""
frequency = {}
max_num = 0
with open(file_path, 'r') as file:
for line in file:
numbers = map(int, line.strip().split())
for num in numbers:
frequency[num] = frequency.get(num, 0) + 1
max_num = max(max_num, num)
# 印出結果
for i in range(1, max_num + 1):
print(f"{i} : {frequency.get(i, 0)}")
效能基準測試
import time
import random
def benchmark_frequency_methods():
"""
效能基準測試
"""
# 產生測試資料
test_sizes = [1000, 10000, 100000]
for size in test_sizes:
arr = [random.randint(1, size) for _ in range(size)]
print(f"\n測試陣列大小: {size}")
# 測試標準計數法
start_time = time.time()
print_frequency_standard(arr.copy())
standard_time = time.time() - start_time
# 測試原地標記法
start_time = time.time()
print_frequency_inplace(arr.copy())
inplace_time = time.time() - start_time
# 測試雜湊表法
start_time = time.time()
print_frequency_hash(arr.copy())
hash_time = time.time() - start_time
print(f"標準計數法: {standard_time:.4f}s")
print(f"原地標記法: {inplace_time:.4f}s")
print(f"雜湊表法: {hash_time:.4f}s")
OAVOService 面試技巧
常見面試變形
- 限制空間複雜度 - 要求 O(1) 空間解法
- 處理負數/零 - 擴展到任意整數範圍
- Top-K頻率 - 只輸出出現次數最多的K個數字
- 即時更新 - 支援動態增刪數字
面試討論要點
- 演算法選擇依據 - 根據資料特徵選擇合適演算法
- 邊界條件處理 - 空陣列、重複元素、越界值
- 擴展性考慮 - 如何支援更大的資料規模
- 實際應用場景 - 日誌分析、使用者行為統計等
複雜度對比
| 方法 | 時間複雜度 | 空間複雜度 | 適用場景 |
|---|---|---|---|
| 標準計數 | O(n) | O(n) | 數字範圍已知且不大 |
| 原地標記 | O(n) | O(1) | 空間受限，數字範圍小 |
| 雜湊表 | O(n) | O(k) | 數字範圍大，稀疏分佈 |
| 分塊處理 | O(n) | O(n/塊數) | 記憶體受限的大陣列 |
OAVOService 專業面試助攻服務 - 我們深度解析各類演算法面試題目，為學員提供 Google、Amazon、Microsoft、Meta 等頂級公司的即時面試輔助。憑藉豐富的面試經驗和演算法優化技巧，助你在程式設計面試中脫穎而出。
如果你正在準備演算法面試，歡迎了解我們的 客製化演算法面試訓練方案 —— 從基礎資料結構到進階優化技巧，全面提升你的程式設計面試競爭力。
標籤: 頻率統計, 陣列演算法, 空間優化, 原地操作, 演算法面試, OAVOService