題目描述:給定一個整數陣列 inventory,代表各個產品的庫存量。定義「平衡庫存」為陣列中每個元素的出現次數都相同。求最少需要丟棄多少個元素,使剩餘的庫存達到平衡。
解題思路:首先統計每個數字的出現次數。假設最終保留 g 組,每組出現 c 次,則保留的元素數為 g * c。需要丟棄的數為 n - g * c。我們需要在所有合法的 (g, c) 組合中找到使 n - g * c 最小(即 g * c 最大)的方案。
合法條件:至少有 g 個不同的數字,且每個被選中的數字至少出現 c 次。因此,先統計各數字的頻率,排序後枚舉 c,用二分搜尋或掃描找到有多少數字的頻率 >= c,即可得到 g。取所有 g * c 的最大值。
時間複雜度:O(n + F * log F) — 統計頻率 O(n),排序 O(F log F),枚舉 c 最多 O(max_freq) 次,每次二分搜尋 O(log F)。F 為不同數字的個數。
空間複雜度:O(F) — 頻率表和排序陣列。
1. Count frequency of each number in inventory 2. Collect all frequencies into array, sort descending 3. For each possible count c from 1 to max_frequency: a. Find g = number of distinct values with frequency >= c (binary search on sorted array) b. Update maxKeep = max(maxKeep, g * c) 4. Return n - maxKeep
枚舉 g(保留的組數):固定保留 g 個不同的數字,每個數字取前 c 個。排序頻率後,取最大的 g 個頻率,c = min(這 g 個頻率)。但取最小值可能不是最優,因為可以選擇更小的 c 來容納更多的 g。
暴力枚舉所有 (g, c) 對:時間 O(F * max_freq),在頻率不大時可行。