2023-09-05：请用 go 语言编写。一个图像有 n 个像素点，存储在一个长度为 n 的数组 arr 里，每个像素点的取值范围 [0,s] 的整数，请你给图像每个像素点值加上一个整数 k（可以是负数），像素值会

作者：福大大架构师每日一题

2023-09-05
北京
本文字数：4454 字
阅读完需：约 15 分钟

2023-09-05：请用 go 语言编写。一个图像有 n 个像素点，存储在一个长度为 n 的数组 arr 里，

每个像素点的取值范围[0,s]的整数，

请你给图像每个像素点值加上一个整数 k（可以是负数），

像素值会自动截取到[0,s]范围，

当像素值<0，会更改为 0，当新像素值>s，会更改为 s，

这样就可以得到新的 arr，想让所有像素点的平均值最接近中位值 s/2, 向下取整。

请输出这个整数 k, 如有多个整数 k 都满足, 输出小的那个。

1 <= n <= 10^6，

1 <= s <= 10^18。

来自华为 OD。

来自左程云。

答案 2023-09-05：

根据代码和题目描述，可以将算法分为以下三种不同的方法：

方法一：暴力方法

这种方法通过枚举 k 的值来计算每个像素值加上 k 后的平均值，然后选择平均值最接近中位值 s/2 的 k。
该方法采用两层循环：外层循环枚举 k 的取值，内层循环计算平均值。
时间复杂度：O(n^2)
空间复杂度：O(1)

方法二：优化暴力方法

这种方法在暴力方法的基础上进行了一些优化，采用二分查找来减少计算的次数。
首先，确定 k 的取值范围为[-s, s]，然后进行二分查找来逼近平均值最接近中位值 s/2 的 k。
时间复杂度：O(n*log(s))
空间复杂度：O(1)

方法三：正式方法（最优解）

这种方法是一种最优解，通过先对数组 arr 进行排序，然后使用前缀和数组 pre 来存储累加和，以便在计算过程中快速计算区间和。
确定 k 的取值范围，根据 k 的正负分别进行二分查找，得到最接近中位值 s/2 的 k。
时间复杂度：O(n*log(n) + log(s)*log(n))
空间复杂度：O(n)

go 完整代码如下：

package main
import (  "fmt"  "math"  "math/rand"  "sort")
// 暴力方法// 为了测试func best1(arr []int, s int) int {  half := s / 2  average := -100000  ans := -s  for k := -s; k <= s; k++ {    curAverage := average1(arr, k, s)    if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) {      average = curAverage      ans = k    }  }  return ans}
// 暴力方法// 为了测试func average1(arr []int, k, s int) int {  sum := 0  for _, num := range arr {    value := num + k    if value < 0 {      sum += 0    } else if value > s {      sum += s    } else {      sum += value    }  }  return sum / len(arr)}
// 优化了一下，但不是最优解func best2(arr []int, s int) int {  l := -s  r := s  m := 0  half := s / 2  average := -s  ans := 0  for l <= r {    m = (l + r) / 2    curAverage := average1(arr, m, s)    if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) ||      (math.Abs(float64(half-curAverage)) == math.Abs(float64(half-average)) && m < ans) {      average = curAverage      ans = m    }    if curAverage >= half {      r = m - 1    } else {      l = m + 1    }  }  return ans}
// 正式方法// 最优解// O(N * logN) + O(logS *  logN)func best3(arr []int, s int) int {  sort.Ints(arr)  sum := make([]int, len(arr))  sum[0] = arr[0]  for i := 1; i < len(arr); i++ {    sum[i] = sum[i-1] + arr[i]  }  l := -s  r := s  m := 0  half := s / 2  average := -s  ans := 0  for l <= r {    m = (l + r) / 2    curAverage := average3(arr, sum, m, s)    if math.Abs(float64(half-curAverage)) < math.Abs(float64(half-average)) ||      (math.Abs(float64(half-curAverage)) == math.Abs(float64(half-average)) && m < ans) {      average = curAverage      ans = m    }    if curAverage >= half {      r = m - 1    } else {      l = m + 1    }  }  return ans}
func average3(arr []int, pre []int, k, s int) int {  n := len(arr)  if k < 0 {    l := bsZero(arr, k)    sum := rangeSum(pre, l+1, n-1)    return (sum + (k * (n - l - 1))) / n  } else {    r := bsS(arr, k, s)    sum := rangeSum(pre, 0, r-1)    return (sum + (k * r) + (s * (n - r))) / n  }}
func bsZero(arr []int, k int) int {  ans := -1  l := 0  r := len(arr) - 1  var m int  for l <= r {    m = (l + r) / 2    if arr[m]+k <= 0 {      ans = m      l = m + 1    } else {      r = m - 1    }  }  return ans}
func bsS(arr []int, k, s int) int {  ans := len(arr)  l := 0  r := len(arr) - 1  var m int  for l <= r {    m = (l + r) / 2    if arr[m]+k >= s {      ans = m      r = m - 1    } else {      l = m + 1    }  }  return ans}
func rangeSum(pre []int, l, r int) int {  if l > r {    return 0  }  if l == 0 {    return pre[r]  }  return pre[r] - pre[l-1]}
// 为了测试func randomArray(n, s int) []int {  arr := make([]int, n)  for i := 0; i < n; i++ {    arr[i] = randInt(0, s)  }  return arr}
func randInt(min, max int) int {  return min + rand.Intn(max-min+1)}
func main() {  N := 50  S := 500  testTimes := 10000  fmt.Println("测试开始")  for i := 0; i < testTimes; i++ {    n := randInt(1, N)    s := randInt(1, S)    arr := randomArray(n, s)    ans1 := best1(arr, s)    ans2 := best2(arr, s)    ans3 := best3(arr, s)    if ans1 != ans2 || ans1 != ans3 {      fmt.Println("出错了！")    }  }  fmt.Println("测试结束")}

复制代码

c++完整代码如下：

#include <iostream>#include <vector>#include <algorithm>
using namespace std;
int average1(vector<int>& arr, int k, int s);int average3(vector<int>& arr, vector<int>& pre, int k, int s);int bsZero(vector<int>& arr, int k);int bsS(vector<int>& arr, int k, int s);int rangeSum(vector<int>& pre, int l, int r);int best1(vector<int>& arr, int s);int best2(vector<int>& arr, int s);int best3(vector<int>& arr, int s);vector<int> randomArray(int n, int s);void test();
int average1(vector<int>& arr, int k, int s) {    int sum = 0;    for (int num : arr) {        int value = num + k;        if (value < 0) {            sum += 0;        }        else if (value > s) {            sum += s;        }        else {            sum += value;        }    }    return sum / arr.size();}
int average3(vector<int>& arr, vector<int>& pre, int k, int s) {    int n = arr.size();    if (k < 0) {        int l = bsZero(arr, k);        int sum = rangeSum(pre, l + 1, n - 1);        return (sum + (k * (n - l - 1))) / n;    }    else {        int r = bsS(arr, k, s);        int sum = rangeSum(pre, 0, r - 1);        return (sum + (k * r) + (s * (n - r))) / n;    }}
int bsZero(vector<int>& arr, int k) {    int ans = -1;    int l = 0;    int r = arr.size() - 1;    int m;    while (l <= r) {        m = (l + r) / 2;        if (arr[m] + k <= 0) {            ans = m;            l = m + 1;        }        else {            r = m - 1;        }    }    return ans;}
int bsS(vector<int>& arr, int k, int s) {    int ans = arr.size();    int l = 0;    int r = arr.size() - 1;    int m;    while (l <= r) {        m = (l + r) / 2;        if (arr[m] + k >= s) {            ans = m;            r = m - 1;        }        else {            l = m + 1;        }    }    return ans;}
int rangeSum(vector<int>& pre, int l, int r) {    if (l > r) {        return 0;    }    return l == 0 ? pre[r] : (pre[r] - pre[l - 1]);}
int best1(vector<int>& arr, int s) {    int half = s / 2;    int average = -100000;    int ans = -s;    for (int k = -s; k <= s; k++) {        int curAverage = average1(arr, k, s);        if (abs(half - curAverage) < abs(half - average)) {            average = curAverage;            ans = k;        }    }    return ans;}
int best2(vector<int>& arr, int s) {    int l = -s;    int r = s;    int m = 0;    int half = s / 2;    int average = -s;    int ans = 0;    while (l <= r) {        m = (l + r) / 2;        int curAverage = average1(arr, m, s);        if ((abs(half - curAverage) < abs(half - average))            || ((abs(half - curAverage) == abs(half - average)) && m < ans)) {            average = curAverage;            ans = m;        }        if (curAverage >= half) {            r = m - 1;        }        else {            l = m + 1;        }    }    return ans;}
int best3(vector<int>& arr, int s) {    sort(arr.begin(), arr.end());    vector<int> sum(arr.size());    sum[0] = arr[0];    for (int i = 1; i < arr.size(); i++) {        sum[i] = sum[i - 1] + arr[i];    }    int l = -s;    int r = s;    int m = 0;    int half = s / 2;    int average = -s;    int ans = 0;    while (l <= r) {        m = (l + r) / 2;        int curAverage = average3(arr, sum, m, s);        if ((abs(half - curAverage) < abs(half - average))            || ((abs(half - curAverage) == abs(half - average)) && m < ans)) {            average = curAverage;            ans = m;        }        if (curAverage >= half) {            r = m - 1;        }        else {            l = m + 1;        }    }    return ans;}
vector<int> randomArray(int n, int s) {    vector<int> arr(n);    for (int i = 0; i < n; i++) {        arr[i] = rand() % (s + 1);    }    return arr;}
void test() {    int N = 50;    int S = 500;    int testTimes = 10000;    cout << "测试开始" << endl;    for (int i = 0; i < testTimes; i++) {        int n = rand() % N + 1;        int s = rand() % S + 1;        vector<int> arr = randomArray(n, s);        int ans1 = best1(arr, s);        int ans2 = best2(arr, s);        int ans3 = best3(arr, s);        if (ans1 != ans2 || ans1 != ans3) {            cout << "出错了!" << endl;        }    }    cout << "测试结束" << endl;}
int main() {    test();    return 0;}