Hard
题目描述
给你一个正整数数组 nums，请你返回 nums 中最长的一个前缀的长度，满足删除这个前缀中的一个元素后，剩下的每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素，那么我们认为每个出现的数字都有相同的出现次数（0）。
示例 1：
输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删除 nums[4] = 5，我们将得到 [2,2,1,1,3,3]，这样每个数字都恰好出现两次。
示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
提示：
2 <= nums.length <= 10^51 <= nums[i] <= 10^5
解题思路
这是一道需要仔细分析的哈希表问题。核心思想是跟踪每个数字的出现频率以及频率的分布，判断删除一个元素后是否能使所有数字的频率相同。
我们需要维护两个哈希表：
count：记录每个数字的出现次数freqCount：记录每个频率值对应的数字个数
对于每个前缀，删除一个元素后能使所有频率相同的情况有以下几种：
- 所有数字频率都是1：删除任意一个数字，其他数字频率仍为1
- 只有一个数字频率为1，其他都相同：删除频率为1的数字
- 所有数字频率都相同且大于1：删除任意一个数字，该数字频率减1，其他保持不变
- 只有一个数字频率比其他数字多1：删除该数字的一个实例
- 只有一个数字：删除它后数组为空
通过维护最小频率minFreq和最大频率maxFreq，以及对应的数字个数，我们可以高效判断当前前缀是否满足条件。
时间复杂度为O(n)，空间复杂度为O(n)。
代码实现
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
unordered_map<int, int> count;
unordered_map<int, int> freqCount;
int maxLen = 0;
int maxFreq = 0;
for (int i = 0; i < nums.size(); i++) {
int num = nums[i];
// 更新频率
if (count[num] > 0) {
freqCount[count[num]]--;
if (freqCount[count[num]] == 0) {
freqCount.erase(count[num]);
}
}
count[num]++;
freqCount[count[num]]++;
maxFreq = max(maxFreq, count[num]);
int len = i + 1;
// 检查是否可以删除一个元素使所有频率相同
if ((maxFreq == 1) || // 所有元素频率都是1
(freqCount.size() == 1 && ((freqCount.begin()->first == 1) ||
(freqCount.begin()->first * freqCount.begin()->second == len - 1))) || // 只有一种频率
(freqCount.size() == 2)) { // 两种频率
if (freqCount.size() == 2) {
auto it1 = freqCount.begin();
auto it2 = next(it1);
int freq1 = it1->first, cnt1 = it1->second;
int freq2 = it2->first, cnt2 = it2->second;
// 确保freq1 < freq2
if (freq1 > freq2) {
swap(freq1, freq2); swap(cnt1, cnt2);
}
// 检查删除一个元素后是否能统一频率
if ((freq1 == 1 && cnt1 == 1) || // 有一个数字频率为1
(freq2 == freq1 + 1 && cnt2 == 1) || // 有一个数字频率比其他多1
(freq2 == 1 && cnt2 == len - freq1 * cnt1)) { // 特殊情况
maxLen = len;
}
} else {
maxLen = len;
}
}
}
return maxLen;
}
};
class Solution:
def maxEqualFreq(self, nums: List[int]) -> int:
count = {}
freq_count = {}
max_len = 0
max_freq = 0
for i, num in enumerate(nums):
# 更新频率
if count.get(num, 0) > 0:
freq_count[count[num]] -= 1
if freq_count[count[num]] == 0:
del freq_count[count[num]]
count[num] = count.get(num, 0) + 1
freq_count[count[num]] = freq_count.get(count[num], 0) + 1
max_freq = max(max_freq, count[num])
length = i + 1
# 检查是否可以删除一个元素使所有频率相同
if (max_freq == 1 or # 所有元素频率都是1
len(freq_count) == 1 or # 只有一种频率
len(freq_count) == 2): # 两种频率
if len(freq_count) == 1:
freq, cnt = next(iter(freq_count.items()))
if freq == 1 or freq * cnt == length - 1:
max_len = length
elif len(freq_count) == 2:
freqs = sorted(freq_count.keys())
freq1, freq2 = freqs[0], freqs[1]
cnt1, cnt2 = freq_count[freq1], freq_count[freq2]
if ((freq1 == 1 and cnt1 == 1) or # 有一个数字频率为1
(freq2 == freq1 + 1 and cnt2 == 1) or # 有一个数字频率比其他多1
(freq2 == 1 and cnt2 == length - freq1 * cnt1)): # 特殊情况
max_len = length
else: # max_freq == 1
max_len = length
return max_len
public class Solution {
public int MaxEqualFreq(int[] nums) {
var count = new Dictionary<int, int>();
var freqCount = new Dictionary<int, int>();
int maxLen = 0;
int maxFreq = 0;
for (int i = 0; i < nums.Length; i++) {
int num = nums[i];
// 更新频率
if (count.ContainsKey(num) && count[num] > 0) {
freqCount[count[num]]--;
if (freqCount[count[num]] == 0) {
freqCount.Remove(count[num]);
}
}
count[num] = count.GetValueOrDefault(num, 0) + 1;
freqCount[count[num]] = freqCount.GetValueOrDefault(count[num], 0) + 1;
maxFreq = Math.Max(maxFreq, count[num]);
int length = i + 1;
// 检查是否可以删除一个元素使所有频率相同
if (maxFreq == 1 || freqCount.Count == 1 || freqCount.Count == 2) {
if (freqCount.Count == 1) {
var pair = freqCount.First();
int freq = pair.Key, cnt = pair.Value;
if (freq == 1 || freq * cnt == length - 1) {
maxLen = length;
}
} else if (freqCount.Count == 2) {
var freqs = freqCount.Keys.OrderBy(x => x).ToArray();
int freq1 = freqs[0], freq2 = freqs[1];
int cnt1 = freqCount[freq1], cnt2 = freqCount[freq2];
if ((freq1 == 1 && cnt1 == 1) ||
(freq2 == freq1 + 1 && cnt2 == 1) ||
(freq2 == 1 && cnt2 == length - freq1 * cnt1)) {
maxLen = length;
}
} else {
maxLen = length;
}
}
}
return maxLen;
}
}
var maxEqualFreq = function(nums) {
const count = new Map();
const freqCount = new Map();
let maxFreq = 0;
let result = 0;
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
// Update frequency counts
if (count.has(num)) {
const oldFreq = count.get(num);
freqCount.set(oldFreq, freqCount.get(oldFreq) - 1);
if (freqCount.get(oldFreq) === 0) {
freqCount.delete(oldFreq);
}
}
const newFreq = (count.get(num) || 0) + 1;
count.set(num, newFreq);
freqCount.set(newFreq, (freqCount.get(newFreq) || 0) + 1);
maxFreq = Math.max(maxFreq, newFreq);
const uniqueNums = count.size;
const len = i + 1;
// Check valid conditions
if (
// All elements appear once
maxFreq === 1 ||
// Only one unique number
uniqueNums === 1 ||
// All but one number appear maxFreq times, one appears once
(freqCount.size === 2 && freqCount.has(1) && freqCount.get(1) === 1 && freqCount.get(maxFreq) * maxFreq === len - 1) ||
// All numbers appear maxFreq times except one appears maxFreq+1 times
(freqCount.size === 2 && freqCount.has(maxFreq) && freqCount.has(maxFreq - 1) && freqCount.get(maxFreq) === 1) ||
// All numbers appear the same frequency and removing one element makes it valid
(freqCount.size === 1 && (maxFreq === 1 || freqCount.get(maxFreq) === 1 || maxFreq * freqCount.get(maxFreq) === len - 1))
) {
result = len;
}
}
return result;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |