【力扣题解】1300. 转变数组后最接近目标值的数组和
😊博主目前也在学习,有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈
文章目录
-
- 一、题目
-
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
-
- 1、思路分析
- 2、代码详解
- 三、本题知识
一、题目
1、题目描述
给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。
如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。
请注意,答案不一定是 arr 中的数字。
2、基础框架
- Java版本框架代码如下:
class Solution { public int findBestValue(int[] arr, int target) { }}
3、原题链接
1300. 转变数组后最接近目标值的数组和
二、解题报告
1、思路分析
(1)先对数组排序,遍历arr数组,在遍历的同时计算前缀和与以arr[i]为value的和(即sum + arr[i]*(n - i)),如果大于target,则直接计算value的值。
2、代码详解
class Solution { public int findBestValue(int[] arr, int target) { Arrays.sort(arr); int sum = 0; int n = arr.length; int res = 0; for(int i = 0;i < n;i++) { if(sum + arr[i]*(n - i) > target) { int value = (target - sum)/(n - i); int low = value*(n - i) + sum; int high = (value + 1)*(n - i) + sum; return (target - low) > (high - target) ? value + 1:value; } sum += arr[i]; } return arr[n -1]; } }
三、本题知识
前缀和