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

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

时间：2023-09-05 10:11:06浏览次数：44  
标签：pre arr return int sum 整数 vector 图像 像素点

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

在这里插入图片描述

标签：pre,arr,return,int,sum,整数,vector,图像,像素点
From： https://www.cnblogs.com/moonfdd/p/17678936.html

相关文章

  • 整数分解方法——腾讯2017春招真题
    如下示例：1：共0种分解方法；2：共0种分解方法；3：3=2+1共1种分解方法；4：4=3+1=2+1+1共2种分解方法；5：5=4+1=3+2=3+1+1=2+2+1=2+1+1+1共5种分解方法6：6=5+1=4+2=4+1+1=3+2+1=3+1+1+1=2+2+1+1=2+1+1+1+1共7种分解方法以此类推，求一任意整数num有几种分解方法？思路：对于数num，按照分解......
  • c++ opencv 16bit tiff图像学习笔记
    1、读取图像基本信息：长、宽、通道数、灰度最大值、最小值、均值、方差值和灰度直方图#include<opencv2/opencv.hpp>usingnamespacecv;usingnamespacestd;intmain(intargc,char**argv){//读入图像Matsrc=imread("C:\\Users\\MingYi-LZQ\\Desktop\\1......
  • 【机哥】基于神经网络的图像去噪器
    鱼弦：全栈领域创作新星创作者、51CTO(Top红人+专家博主)、github开源爱好者（go-zero源码二次开发、游戏后端架构https://github.com/Peakchen）基于神经网络的图像去噪器是一种利用深度学习技术来降低图像噪声的方法。它通过训练一个神经网络模型，将含有噪声的图像作为输入，输出一张更......
  • 探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅
    探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅1.简介1.1背景关键信息抽取(KeyInformationExtraction,KIE)指的是是从文本或者图像中，抽取出关键的信息。针对文档图像的关键信息抽取任务作为OCR的下游任务，存在非常多的实际应用场景，如表单识别、车票信息抽取、......
  • 探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅
    探索图像数据中的隐藏信息：语义实体识别和关系抽取的奇妙之旅1.简介1.1背景关键信息抽取(KeyInformationExtraction,KIE)指的是是从文本或者图像中，抽取出关键的信息。针对文档图像的关键信息抽取任务作为OCR的下游任务，存在非常多的实际应用场景，如表单识别、车票信息抽取、......
  • Java正整数除法向上取整
    1、简介在今天刷每日一题的时候看到的，感觉和以前自己写的向上取证的写法比起来好很多，在此记录。来源：1921.消灭怪物的最大数量-力扣（LeetCode）2、内容仅仅在正整数除法，三种都可用1、Math.ceil()2、x/y+(x%y==0?0:1)3、(x-1)/y+1classSolution{publicstaticvoidma......
  • 2023-09-03：用go编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数
    2023-09-03：用go语言编写。给你一个n个节点的无向无根树，节点编号从0到n-1给你整数n和一个长度为n-1的二维整数数组edges，其中edges[i]=[ai,bi]表示树中节点ai和bi之间有一条边。再给你一个长度为n的数组coins，其中coins[i]可能为0也可能为1，1表示节......
  • 2023-09-03：用go编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数
    2023-09-03：用go语言编写。给你一个n个节点的无向无根树，节点编号从0到n-1给你整数n和一个长度为n-1的二维整数数组edges，其中edges[i]=[ai,bi]表示树中节点ai和bi之间有一条边。再给你一个长度为n的数组coins，其中coins[i]可能为0也可能为1，1......
  • 编写判断一个正整数是否为素数的函数
    编写判断一个正整数是否为素数的函数自己搞的，还请斧正。#include <stdio.h>void  prime(int m);                         int main(){    int a[10],i;      for(i=0;i<10;i++)    {        scanf("%d",&a[......
  • Lnton 羚通算法算力云平台如何在 OpenCV-Python 中使用 cvui 库创建图像
    CVUI之图像Pythonimportnumpyasnpimportcv2importcvuidefimage_test():WINDOW_NAME='Image-Test'#创建画布frame=np.zeros((400,600,3),np.uint8)#读取图像image=cv2.imread("lena-face.jpg",cv2.IMREAD_COLOR)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99