如何用最坏情况线性时间算法求数组元素对应min(d1(A[i]),d2(A[i]))的最大值

问题回顾 #

给定大小为n的数组A，以及数值x1、x2，定义：

• d1(m)：数组A中值在x1和m之间（包含端点）的元素数量
• d2(m)：数组A中值在x2和m之间（包含端点）的元素数量

需要在最坏线性时间内，找到所有A[i]对应的min(d1(A[i]),d2(A[i]))的最大值。

核心思路 #

你之前的思路聚焦于单独计算d1、d2的最大值，但min(d1,d2)的最大值并非两者最大值的较小值——它需要找到某个元素A[i]，让d1(A[i])和d2(A[i])的最小值尽可能大。我们可以通过分区间遍历+线性统计实现。

具体步骤 #

1. 预处理基础统计量

遍历数组一次，统计以下信息：

• 针对x1：
  • less1：元素小于x1的数量
  • eq1：元素等于x1的数量
  • cnt_geq_x1：元素大于等于x1的数量（eq1 + (n - less1 - eq1)）
  • cnt_leq_x1：元素小于等于x1的数量（less1 + eq1）
• 针对x2：
  • 同理统计less2、eq2、cnt_geq_x2、cnt_leq_x2
• 同时将数组元素分为三个组：
  • group1：所有≤x1的元素
  • group2：所有在x1和x2之间的元素（若x1>x2则交换两者，不影响结果）
  • group3：所有≥x2的元素

2. 分区间计算最大min值

组3（元素≥x2）

对任意a∈group3：

• d1(a) = cnt_geq_x1 - 数组中大于a的元素数
• d2(a) = cnt_geq_x2 - 数组中大于a的元素数
  由于cnt_geq_x1 ≥ cnt_geq_x2，min(d1(a),d2(a))等价于cnt_geq_x2 - 数组中大于a的元素数。要最大化这个值，取group3中的最大元素（此时无元素大于它），对应值为cnt_geq_x2。

组1（元素≤x1）

对任意a∈group1：

• d1(a) = cnt_leq_x1 - 数组中小于a的元素数
• d2(a) = cnt_leq_x2 - 数组中小于a的元素数
  由于cnt_leq_x1 ≤ cnt_leq_x2，min(d1(a),d2(a))等价于cnt_leq_x1 - 数组中小于a的元素数。要最大化这个值，取group1中的最大元素，对应值为cnt_leq_x1 - 数组中小于该元素的数量（即数组中≥该元素且≤x1的元素总数）。

组2（元素在x1和x2之间）

对任意a∈group2：

• d1(a) = eq1 + group2中≤a的元素数（x1到a的元素总数，包含x1和a）
• d2(a) = eq2 + group2中≥a的元素数（a到x2的元素总数，包含a和x2）
  遍历group2所有元素，计算每个元素的min(d1(a),d2(a))，记录最大值即可。这一步是O(k)时间（k为group2大小，≤n），符合线性要求。

3. 汇总结果

取组1、组2、组3的最大min值中的最大值，就是最终答案。

为什么这是线性时间 #

所有步骤仅需遍历数组常数次：预处理1次，分区间计算各1次，总时间复杂度为O(n)，满足最坏情况下线性时间的要求。

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