LeetCode 1608题解：特殊数组特征值的算法优化

1. 问题背景与题目解析

今天我们来拆解一道LeetCode中等难度题目——1608. 特殊数组的特征值。这道题在周赛和日常练习中出现的频率较高，也是面试中考查基础算法能力的常见题型。题目描述如下：

给定一个非负整数数组nums，如果存在一个数x，使得nums中恰好有x个元素大于等于x，那么称x为这个数组的"特征值"。你的任务是找出数组的所有特征值中最大的那个，如果不存在特征值则返回-1。

举个例子：

• 输入：[3,5] 输出：2 解释：有2个元素（3和5）大于等于2
• 输入：[0,0] 输出：-1 解释：没有满足条件的x

2. 暴力解法与初步优化

2.1 最直观的暴力解法

对于刚接触这道题的新手，最容易想到的就是暴力枚举法。具体思路是：

1. 遍历所有可能的x值（从0到数组长度n）
2. 对每个x，统计数组中≥x的元素个数
3. 如果个数等于x，则记录这个特征值
4. 最后返回最大的特征值或-1

def specialArray(nums): n = len(nums) for x in range(n + 1): count = sum(1 for num in nums if num >= x) if count == x: return x return -1

这个解法的时间复杂度是O(n²)，因为外层循环n+1次，内层统计count又是O(n)。对于小规模数据（n≤100）尚可接受，但显然不是最优解。

2.2 第一次优化：排序预处理

观察到数组元素的顺序不影响结果，我们可以先对数组进行排序。排序后，对于给定的x，我们可以用二分查找快速确定≥x的元素数量，将时间复杂度降到O(n log n)。

def specialArray(nums): nums.sort() n = len(nums) for x in range(n + 1): # 使用bisect找到第一个≥x的位置 idx = bisect.bisect_left(nums, x) count = n - idx if count == x: return x return -1

这里使用了Python内置的bisect模块实现二分查找。虽然时间复杂度有所改善，但仍有优化空间。

3. 最优解法：逆向思维与计数排序

3.1 计数排序思想

更进一步，我们可以利用计数排序的思想。注意到x的取值范围是0到n（数组长度），我们可以：

1. 创建一个大小为n+2的计数数组count（+2是为了处理边界情况）
2. 统计每个数字出现的次数
3. 从后向前累加，得到≥当前x的元素总数

def specialArray(nums): n = len(nums) count = [0] * (n + 2) for num in nums: count[min(num, n)] += 1 total = 0 for x in range(n, -1, -1): total += count[x] if total == x: return x return -1

这个算法的时间复杂度是O(n)，空间复杂度也是O(n)，是最优解法。

3.2 为什么这个解法更高效

关键在于我们避免了重复计算。在暴力解法中，对于每个x都要遍历整个数组统计≥x的元素数量。而通过计数排序的思想，我们只需要：

1. 一次遍历统计各数字出现次数（O(n)）
2. 一次反向遍历累加计数（O(n)）

这样就避免了嵌套循环带来的性能损耗。

4. 边界条件与测试用例

4.1 常见边界情况

在实现时需要注意以下边界条件：

1. 空数组：应返回-1
2. 全0数组：应返回-1
3. 全相同数字的数组：如[3,3,3]，应返回3
4. 连续数字数组：如[0,1,2,3]，应返回2
5. 随机测试用例：如[3,6,7,7,0]，应返回3

4.2 测试代码示例

def test_specialArray(): assert specialArray([]) == -1 assert specialArray([0,0]) == -1 assert specialArray([3,5]) == 2 assert specialArray([0,4,3,0,4]) == 3 assert specialArray([3,6,7,7,0]) == 3 assert specialArray([1,1,2,2]) == 2 print("All tests passed")

5. 算法复杂度对比

让我们总结一下三种解法的性能差异：

在实际面试或竞赛中，建议优先实现计数排序的解法，既能保证效率，代码也相对简洁。

6. 实际编码中的注意事项

6.1 语言特性利用

不同语言可以利用各自的特性简化实现：

• Python：使用bisect模块简化二分查找
• Java：Arrays.sort()和Arrays.binarySearch()
• C++：STL中的sort和lower_bound

6.2 调试技巧

在实现过程中，可以添加打印语句帮助调试：

print(f"x={x}, count={count}") # 查看中间结果

6.3 常见错误

1. x的取值范围错误：应该是0到n（包含n）
2. 二分查找边界处理不当：注意等号条件的处理
3. 计数数组大小不足：需要n+2的大小
4. 累加方向错误：必须从大到小累加

7. 相似题型与扩展思考

7.1 相似题目推荐

掌握了这道题后，可以尝试以下相似题目：

• 274. H指数（同样涉及元素计数与比较）
• 41. 缺失的第一个正数（计数思想的变种）
• 448. 找到所有数组中消失的数字（计数技巧应用）

7.2 算法思想延伸

这道题体现的计数思想在其他场景也很实用：

1. 统计频率分布
2. 处理有限范围内的离散值
3. 替代部分排序需求
4. 作为更复杂算法的预处理步骤

7.3 性能优化启示

从这道题的优化过程中，我们可以学到：

1. 排序往往是优化的第一步
2. 计数统计可以避免重复计算
3. 逆向思维有时能发现更优解
4. 空间换时间是常见的优化手段

8. 实际应用场景

虽然这是一道算法题，但类似的计数思想在实际开发中很常见：

1. 用户行为分析：统计达到某些阈值的用户数量
2. 性能监控：统计超过某响应时间的请求数
3. 推荐系统：筛选满足某些条件的物品数量
4. 数据清洗：统计符合特定条件的数据点

9. 个人刷题心得

在解决这类计数问题时，我总结了几个实用技巧：

1. 先考虑暴力解法，确保理解题意
2. 观察数据范围，寻找优化空间
3. 画图或举例帮助理解问题本质
4. 注意边界条件，特别是0和最大值
5. 测试用例要覆盖各种特殊情况

对于这道题，我最初实现的是排序+二分解法，后来在讨论区看到计数排序的解法，才意识到可以进一步优化。这提醒我们，刷题后查看其他人的优秀解法也很重要。