如何在O(n)时间内找出B中不在A的最小元素（无哈希、B为A两倍大）

情况1：元素为整数且范围可控（如范围在O(n)内） #

可以用桶计数法，时间复杂度严格O(n)，不使用哈希表：

• 遍历数组A，用一个数组作为计数桶（索引对应元素值），统计每个元素的出现次数。
• 遍历数组B，用同样的计数桶统计每个元素的出现次数。
• 从小到大遍历计数桶，找到第一个「B中计数 > A中计数」的元素，即为答案：
  • 若元素在A中完全不存在，A中计数为0、B中计数≥1，符合条件；
  • 若元素在A中存在，但B中出现次数更多，多出来的部分属于B的额外元素，也符合要求。

情况2：元素范围不可控，但允许平均O(n)时间复杂度 #

可以用快速选择算法变种：

• 找到B数组中的最小元素x；
• 遍历A数组统计x的出现次数countA，同时统计x在B中的出现次数countB；
• 若countB > countA，x就是答案，直接返回；
• 若countB == countA，说明B中所有x的实例都来自A，排除B中所有x后，在剩余元素中重复上述流程。
• 该方法平均时间复杂度为O(n)，但最坏情况为O(n²)（例如A是[1,2,...,n]，B是[1,2,...,n,n+1,...,2n]）。

情况3：元素为任意类型（如字符串）且无范围限制 #

不存在严格O(n)时间的解法。因为验证一个元素是否属于A必须遍历A数组（O(n)时间），最坏情况下需要验证O(n)个元素，总时间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者pparker