LeetCode 1300. 转变数组后最接近目标值的数组和
2021-05-13 12:29
标签：目标 mat 题目 ems new 下标 组元 ndis arc 1300. 转变数组后最接近目标值的数组和 这个题是昨天的每日一题，昨天太忙了，没来得及写完。但是有了思想，本地上跑了几次发现跑出来的答案又误差就溜掉了。 有个很奇怪的地方，自己写的反而不如直接调用系统库中的Arrays.binarySearch()方法快。醉了 LeetCode 1300. 转变数组后最接近目标值的数组和 标签：目标 mat 题目 ems new 下标 组元 ndis arc 原文地址：https://www.cnblogs.com/ZJPaang/p/13129813.html
今天有空了就来填一下坑。class Solution {
public int findBestValue(int[] arr, int target) {
//先进行排序，取得搜索的边界，边界就是0到数组元素中的最大值
Arrays.sort(arr);
//这个前缀和数组还是非常重要的，这个长度一定要多一，否则就会像之前做的一样搜出来的值不对。
int[] prefixSum = new int[arr.length + 1];
//计算前缀和数组
for(int i = 1; i = target){
right = mid;
}else{
left = mid + 1;
}
}
return right;
}
}
说起二分查找 ，这个题的确有点像我之前做过的二分查找变种题，具体请看这里
不过这个题还有更快的方法，就是双重二分查找，我昨天第一次写的时候就是双重二分查找，对于我们寻找的ans进行二分查找，然后在循环体内查找当前可能的答案在arr数组中的位置，等到有时间了我再来补上这个坑。
上一篇：v-for列表排序
下一篇：Python编码问题
文章标题：LeetCode 1300. 转变数组后最接近目标值的数组和
文章链接：http://soscw.com/index.php/essay/85142.html