P3310. 平均像素值

解题思路

关键限制条件

如果题目描述中没有以下这句话，那么本题非常简单：

> 新图的像素值会自动截取到 [0, 255] 范围。当新像素值 < 0，其值会更改为 0；当新像素值 > 255，其值会更改为 255；例如 newImg = "-1 -2 256"，会自动更改为 "0 0 255"。

由于上述这个限制，当我们选取一个特定的值 k 的时候，原数组并不会整体增加 n * k（其中 n 是原数组的长度）。

问题的二段性

我们考虑这个问题的二段性：

• 当 k 取一个绝对值很大的负数时，譬如 -255，那么所有像素值均会被更改为 0，此时新数组平均数为 0。
• 当 k 取一个绝对值很大的正数时，譬如 255，那么所有像素值均会被更改为 255，此时新数组平均数为 255。

因此，存在一个特定的 k = ans，能够使得新数组的所有像素值的平均值恰好大于等于 128。此时 k = ans 和 k = ans - 1 这两个数，都是有可能使得像素值最接近 128 的结果，再加上一个判断即可。

上述二段性问题显然可以直接使用二分查找来完成。

子问题：计算新数组的平均值

接下来考虑二分查找的子问题 cal_new_average(nums, k, n)。

在确定了某一个特定的 k 的情况下，我们可以非常方便地计算出新数组的平均值。其过程如下：

1. 遍历原数组中的每一个数字 num，将其 +k 得到修改后的新元素 new_num。 2. 在遍历中，若：

• new_num 的值小于 0，则将其设置为 0。
• new_num 的值大于 255，则将其设置为 255。

3. 将 new_num 的值加入一个新的变量 new_sum 中，表示新数组的和。 4. 遍历结束后，计算 new_sum / n 作为函数返回值。

二分查找主框架

剩余的二分主框架部分，就是直接套模板了。

复杂度分析 设 n 为像素点个数（数组 img 的长度）。

• cal_new_average 对数组做一趟遍历，逐个加 k、截断到 [0, 255] 后求和取平均，单次调用为 O(n)。
• 二分的搜索对象是整数 k，取值范围固定为 [-255, 256)，共 511 个候选值，迭代次数为 log 511 约 9 次，是与 n 无关的常数。
• 二分结束后还要各调用一次 cal_new_average，比较 left-1 与 left 两个候选谁的平均值更接近 128，为 O(n)。

因此总时间复杂度为 O(n)（严格写是 O(n log 511)，其中 log 511 不超过 10，可视为常数因子），瓶颈只在每轮对整个数组的一趟扫描。空间上只用 new_sum、new_num 等常数个变量，除输入外额外空间复杂度为 O(1)。