首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

2023-09-05:请用go语言编写。一个图像有n个像素点,存储在一个长度为n的数组arr里, 每个像素点的取值范围[0,s]

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

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

请你给图像每个像素点值加上一个整数k(可以是负数),

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

当像素值s,会更改为s,

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

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

1

1

来自华为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完整代码如下:

在这里插入图片描述c++完整代码如下:

在这里插入图片描述

  • 发表于:
  • 原文链接https://page.om.qq.com/page/OO_Cudz7uIA9M5mFYjLHtNFQ0
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

相关快讯

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券