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(nlog(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;
}

本栏目推荐文章
• 类模板实现简单的数组
• CxImage 加载图像大小限制
• 数组内存图
• 数组
• OpenCV计算机视觉学习（15）——浅谈图像处理的饱和运算和取模运算
• Spark读写达梦数据库报错Decimal精度为负数以及解决方案
• 整数的划分（递归或动态规划）
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• 吴师兄学算法day06 双指针 80. 合并两个有序数组
• C# 方法中的参数数组

像素 整数 图像 负数 数组像素 整数 图像 负数 数组 负数 个位 整数 逆序 整数 形式 负数 负数 整数enum 负数 小数 整数input 图像 原点 坐标 像素 负数 进制 数组 字节 下标 负数 数组 像素 全方位 图像 技术 数组 项目 景区 负数