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完整代码如下：
代码语言：javascript复制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 完整代码如下：
代码语言：javascript复制#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;
}
在这里插入图片描述
