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
#include
#include
using namespace std;
int average1(vector
int average3(vector
int bsZero(vector
int bsS(vector
int rangeSum(vector
int best1(vector
int best2(vector
int best3(vector
vector
void test();
int average1(vector
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 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 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 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
if (l > r) {
return 0;
}
return l == 0 ? pre[r] : (pre[r] - pre[l - 1]);
}
int best1(vector
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 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
sort(arr.begin(), arr.end());
vector
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
vector
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 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;
}
推荐文章
发表评论