数组 + 区间
240 搜索二维数组矩阵
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：从最左下坐标开始
仔细观察矩阵左下角或者右上角，对于左下角，==往右走数字变大，往上走数字变小==，
那么我们从左下角出发，target比当前值大，我们就往右走，target比当前值小，我们就往上走，若target存在一定会找到
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) return false;
int i = matrix.size() - 1;
int j = 0;
while(i >= 0 && j < matrix[0].size()){
if(matrix[i][j] > target)
--i;
else if(matrix[i][j] < target)
++j;
else return true;
}
return false;
}
};1248 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
思路：
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0,cnt = 0;
int odd[n+2];
for(int i = 0;i < n;++i){
if(nums[i]%2 == 1)
odd[++cnt] = i;
}
odd[0] = -1,odd[++cnt] = n;//边界处理
for(int i = 1;i + k <= cnt;++i){
ans += (odd[i] - odd[i - 1]) * (odd[i + k ] - odd[i + k - 1]);
}
return ans;
}
};数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
思路：
利用归并算法，在出现逆序归并情况时，更新计数器
如：
当nums[i] > nums[j]时，意味着nums[i] 相对于 nums[j]是逆序的，之间的距离是j-i但是考虑到后面的归并，j的位置也不是不变的，因此，至少对于 [i:mid]这段距离是逆序的， 需要将计数器加上(mid - i + 1)
class Solution {
public:
int mergeSort(vector<int>& nums,vector<int>& tmp,int left,int right){
if(left >= right) return 0;
int mid = left + (right - left) / 2;
int cnt = mergeSort(nums,tmp,left,mid) + mergeSort(nums,tmp,mid + 1,right);
int i = left,j = mid + 1;
int k = left;
while(i <= mid && j <= right){
if(nums[i] <= nums[j]){
tmp[k++] = nums[i++];
}else{
tmp[k++] = nums[j++];
cnt += (mid - i + 1);
}
}
while(i <= mid){
tmp[k++] = nums[i++];
}
while(j <= right){
tmp[k++] = nums[j++];
}
//将当前有序数组tmp更新到nums中去
copy(tmp.begin() + left, tmp.begin() + right + 1, nums.begin() + left);
return cnt;
}
int reversePairs(vector<int>& nums) {
int n = nums.size();
vector<int> tmp(n);
return mergeSort(nums,tmp,0,n-1);
}
};如果要把一个序列（sequence）拷贝到一个容器（container）中去，通常用std::copy算法，代码如下：
std::copy(start, end, std::back_inserter(container));
这里，start和end是输入序列（假设有N各元素）的迭代器（iterator），container是一个容器，该容器的接口包含函数push_back。假设container开始是空的，那么copy完毕后它就包含N个元素，并且顺序与原来队列中的元素顺序一样。标准库提供的back_inserter模板函数很方便，因为它为container返回一个back_insert_iterator迭代器，这样，复制的元素都被追加到container的末尾了。
33 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
思路：
若nums[mid] != target
先判断是左区间有序还是右区间有序，再判断target在左区间还是在右区间。
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0,right = n - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
if(nums[left] <= nums[mid]){//左区间有序
if(nums[left] <= target && target <= nums[mid]){//target在左区间
right = mid - 1;
}else{//target在右区间
left = mid + 1;
}
}else{//右区间有序
if(nums[mid] <= target && target <= nums[right]){//target在右区间
left = mid + 1;
}else{//target在左区间
right = mid - 1;
}
}
}
return -1;
}
};56 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
思路：
让我们先来考虑一个比较简单的问题：
如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？
答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 000，不同结果为 111。那么在计算过程中，成对出现的数字的所有位会两两抵消为 000，最终得到的结果就是那个出现了一次的数字。
那么这一方法如何扩展到找出两个出现一次的数字呢？
如果我们可以把所有数字分成两组，使得：
两个只出现一次的数字在不同的组中；
相同的数字会被分到相同的组中。
那么对两个组分别进行异或操作，即可得到答案的两个数字。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i = 0;i < n;++i){
sum ^= nums[i];
}
int first = 1;
while((sum & first ) == 0){
first <<= 1;
}
int a = 0,b = 0;
for(int i = 0;i < n;++i){
if(nums[i] & first){
a ^= nums[i];
}else{
b ^= nums[i];
}
}
return vector<int> {a,b};
}
};最大重叠区间个数
已知小猪每晚都要约好几个女生到酒店房间。每个女生 i 与小猪约好的时间由 [si , ei］表示，其中 si 表示女生进入房间的时间， ei 表示女生离开房间的时间。由于小猪心胸开阔，思想开明，不同女生可以同时存在于小猪的房间。请计算出小猪最多同时在做几人的「多人运动」。
例子：
Input ： [[ 0 , 30] ,[ 5 , 10 ] ， [15 , 20 ] ]
OutPut ：最多同时有两个女生的「三人运动」
思路
直觉：
我们来看下有哪些情况，看是否可以打开思路。 如下图：
（上面的情况，那么最大的人数是1，下面的情况最大的人数是2）
不难发现，除了关心开始时间，我们应该同样关心结束时间。 如果”相邻“的区间重合，则人数++，最后返回人数即可。
具体算法：
- 按照女孩约会的开始时间进行一次升序排序
然后用一个小顶堆，维护当前每个女孩约会的结束时间
[](https://camo.githubusercontent.com/443f2fd1c80617bb3b1356005429c6a69e5242cf/68747470733a2f2f747661312e73696e61696d672e636e2f6c617267652f30303753385a496c6c7931676538387567623931696a333063613036656466792e6a7067)- 然后当一个新的女孩出现的时候，判断一下是否和上一个女孩有重叠，如果有则入堆，即多人运动的人数+1。没有重叠的话（人数不变），我们可以弹出一个元素，保持堆的人数不变。
- 堆的大小表示的就是多人运动的最大人数，返回堆的大小即可。
代码（C++）
class Solution {
public:
int np(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>&b){
return a[0] < b[0];
});
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < intervals.size(); i++) {
// 没重叠，弹出堆顶元素，并维持最小堆的性质不变
if (!heap.empty() && heap.top() <= intervals[i][0]) {
heap.pop();
}
// 女孩++
heap.push(intervals[i][1]);
}
return heap.size();
}
};hash法
#include <bits/stdc++.h>
using namespace std;
#define up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
#define girl pair<int,int> //first开始时间,second结束时间
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const int maxn = 1001; //小猪每晚最多约的女生数量
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n; //小猪今晚约了n个女孩
cin >> n;
vector<girl> v;
up(i,1,n)
{
int bg,ed;
cin >> bg >> ed;
v.push_back(mp(bg,ed));
}
int cnt[maxn]; //cnt[i]记录i时刻的多人运动人数
ms(cnt,0);
int ans = -INF;
up(i,0,n-1) //枚举
{
up(j,v[i].first,v[i].second)
{
cnt[j]++;
ans = max(ans,cnt[j]);
}
}
cout << ans << endl;
return 0;
}区间合并
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end());
int n = intervals.size();
vector<vector<int>> ans;
vector<int> cur;
if(intervals.size() == 0 || (intervals.size() == 1)) return intervals;
cur = intervals[0];
for(int i = 1;i < n;++i){
if(intervals[i][0] <= cur[1] && intervals[i][1] >= cur[1]){
cur[1] = intervals[i][1];
}
if(intervals[i][0] > cur[1]){
ans.push_back(cur);
cur = intervals[i];
}
if(i == n - 1)
ans.push_back(cur);
}
return ans;
}
};区间重叠
给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。
返回这两个区间列表的交集。
（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）
示例：
输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意：输入和所需的输出都是区间对象组成的列表，而不是数组或列表。
思路：
双指针遍历
注意重叠区间是：{max(a1,b1),min(a2,b2)}
b2 < a2 时j++;其他情况：i++
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
int i = 0,j = 0;
vector<vector<int>> ans;
vector<int> cur;
while(i < A.size() && j < B.size()){
int a1 = A[i][0],a2 = A[i][1];
int b1 = B[j][0],b2 = B[j][1];
if(b2 >= a1 && b1 <= a2){
ans.push_back({max(a1,b1),min(a2,b2)});
}
if(b2 < a2){
j++;
}else{
i++;
}
}
return ans;
}
};有序矩阵中的第k个最小数组和
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1：
输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2：
输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17
示例 3：
输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4：
输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12
提示：
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组
思路：
暴力解决法：每次多考虑一行，然后始终保证考虑后能取到第k小的结果
使用 vector<int> 记录各个行选一个数相加的和
- 记录的方法是，先保存第一行各数
- 然后把第二行的各数拿出来，组合相加
- 对其排列，超过 k 个就不需要保留了
相加之后记录回 ans ，下次拿出第三行各数，与其组合相加
返回第 k 个最小数组和
class Solution {
public:
int kthSmallest(vector<vector<int>>& mat, int k) {
int m=mat.size();
int n=mat[0].size();
vector<int> res(mat[0]);//将mat[0]的一串数字赋值给res
for(int i=1;i<m;++i)
{
multiset<int> st;
for(int x:res)
{
for(int y:mat[i])
{
st.insert(x+y);
}
}//计算出前两行所有可能的解，放到st中，赋值给res，res代表着之前所有行的相加的所有可能解
res.assign(st.begin(),st.end());
res.resize(min(k,(int)res.size()));//对res长度随时进行修剪，丢去不必要的计算
}
return res[k-1];
}
};思路二：
先确定左右边界，即最小和与最大和，然后二分得到mid，每次判断和小于mid的数组有多少个，如果大于等于k那么更新r，否则更新l。
class Solution {
public:
//maxSum目标数组和，idx为当前的数组所在行,sum为当前数组和,cnt为第k大的意思
//数组和小于等于maxSum的不少于cnt个的数组
void dfs(vector<vector<int>>& mat, int k, int maxSum, int idx, int sum, int& cnt) {
if (idx == mat.size()) return;//每一行都扫描了
if (sum > maxSum || cnt > k) return;
//当期数组和超过目标数组和或者小于maxSum的数组和个数超过了k，及时剪枝
//当前行不选其他数字，直接到下一行去选择
dfs(mat, k, maxSum, idx + 1, sum, cnt);
for (int j = 1; j < mat[idx].size(); j++) {
int temp = sum + mat[idx][j] - mat[idx][0];//计算在只替换idx行某个数字时对应的数组和
if (temp > maxSum) break;//数组和太大了，跳出
cnt++;//比上个数组和大1，cnt++,到下一行深度优先搜索选数字
dfs(mat, k, maxSum, idx + 1, temp, cnt);
}
}
int kthSmallest(vector<vector<int>>& mat, int k) {
int l = 0;
int r = 0;
for (int i = 0; i < mat.size(); i++) {
l += mat[i].front();
r += mat[i].back();
}
//l为最小数组和，r为最大数组和
int base = l;
while (l < r) {
int mid = l + (r - l) / 2;
int cnt = 1;
dfs(mat, k, mid, 0, base, cnt);
if (cnt < k) {
l = mid + 1;
}
else {
r = mid;
}
}
return r;
}
};小张刷题计划
为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。
在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。
我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。
示例 1：
输入：time = [1,2,3,3], m = 2
输出：3
解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。
这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。
思路:
题意概述
给定一个数组，将其划分成 M 份，使得每份元素之和最大值最小，每份可以任意减去其中一个元素。
题解
如果不考虑每份可以任意减去一个元素，就是一个经典的二分问题，具有单调最优的性质：如果最大值为 t 可以满足条件划分，那么最大值为 t+1也可以。所以就直接二分最大值 t，找到最小满足条件的 t 即可。
本题加了一个条件：每份可以删除任意一个数组。为了能够让最大值最小，显然每份中删去的一定是最大元素，所以在二分判定可行性时，维护当前序列的最大值，然后记录删除最大值的结果，也就是说二分的判定是：是否可以让每组删除最大值之后，总和都小于等于 t。
- 找到一个数，把它作为分割后各个子数组的和的最大值
- 根据这个最大值，分割数组，使每个子数组的和都不超过这个最大值,根据题意顺序填充子数组
使用二分查找来确定这个值
- int l = 0;
- int r = INT_MAX; 注意这个值有可能比单一一个值还大
- 如果不能将数组中所有数字都分割进子数组，则表示这个最大值不够大
- 如果提前分割完了，说明这个值取得太大了
class Solution {
public:
int minTime(vector<int>& time, int m) {
if (time.size() <= m) return 0;
int l = 0;
int r = INT_MAX;
while (l < r) {
int mid = l + (r - l) / 2;
if (canSplit(time, m, mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
return r;
}
//对time数组进行分割判断，是否在分数组总和为split_sum，分组个数最多为m情况下可以分割
bool canSplit(vector<int>& time, int m, int split_sum) {
int cnt = 0;
int sum = 0;
int maxT = 0;
for (auto& t : time) {
sum += t;//sum计算数组元素之和
maxT = max(maxT, t);//maxT计算当前子数组的最大值
if (sum - maxT > split_sum) {//如果去掉了子数组最大值后的子数组的和超过split_sum
if (++cnt == m) return false;
//当前分组个数+1,如果分组个数超出要求则说明当前方案不可行
sum = t;//计算新的子数组
maxT = t;//更新子数组最大值
}
}
return true;
}
};
分割数组的最大值
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)
示例:
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
思路：
解题思路：
由题意可知：子数组的最大值是有范围的，即在区间[max(nums),sum(nums)] 之中。
令 l=max(nums)，h=sum(nums)`mid=(l+h)/2`计算数组和最大值不大于mid对应的子数组个数 cnt(这个是关键！)
如果 cnt>m，说明划分的子数组多了，即我们找到的 mid 偏小，故 l=mid+1；
否则，说明划分的子数组少了，即 mid 偏大(或者正好就是目标值)，故 h=mid。
#define LL long long
class Solution {
public:
bool isOverflow(vector<int>& nums,int m,long split_sum){
long sum = 0,cnt = 0;
for(auto x:nums){
sum += x;
if(sum > split_sum){
if(x > split_sum) return false;
if(++cnt == m) return false;
sum = x;
}
}
if(sum > split_sum) return false;
return true;
}
int splitArray(vector<int>& nums, int m) {
long left = nums[0], right = 0;//int类型在这里不合适，因为h可能会超过int类型能表示的最大值
for (auto i : nums)
{
right += i;
left = left > i ? left : i;
}
while(left <= right){
long mid = left + (right - left) / 2;
if(isOverflow(nums,m,mid)){
right = mid - 1;
}else{
left = mid + 1;
}
}
return left;
}
};面试题29 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
算法：
设计矩形四个点的坐标，每次打印从这些坐标点为基准开始
如果上方和右方已经打印完的情况下，四个顶点的位置不满足 top <= bottom && left <= right 就不需要再打印下方和左方的数字了，不然会发生重复打印的情况
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if(matrix.size() == 0 || matrix[0].size() == 0){
return {};
}
int rows = matrix.size();
int cols = matrix[0].size();
int top = 0,bottom = rows - 1,left = 0,right = cols - 1;
while(top <= bottom && left <= right){
for(int col = left;col <= right;col++){
ans.push_back(matrix[top][col]);
}
for(int row = top + 1;row <= bottom;row++){
ans.push_back(matrix[row][right]);
}
if(top < bottom && left < right){
for(int col = right - 1; col > left;col--){
ans.push_back(matrix[bottom][col]);
}
for(int row = bottom;row > top;row--){
ans.push_back(matrix[row][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return ans;
}
};面试题50 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
算法：
建立一个map，存储字符以及出现次数
//无序哈希表法
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> mm;
for (char& ch : s) ++mm[ch];
for (char& ch : s) if (mm[ch] == 1) return ch;
return ' ';
}
};
//有序哈希表法
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> mm;
int t[26] = { INT_MAX };
for (int i = 0; i < s.size(); ++i) {
++mm[s[i]];
t[s[i] - 'a'] = i;//多个同样的重复字符中的最后一个在数组的位置存在t中，只有一个字符出现的自然就只有一个位置
}
char ans = ' ';
int mint = INT_MAX;
for(auto& p:mm) //出现次数为1 并且 字符位置最靠前的
if (p.second == 1 && t[p.first - 'a'] < mint) {
ans = p.first;
mint = t[p.first - 'a'];
}
return ans;
}
};1300 转变数组后最接近目标值的数组和
给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。
示例 1：
输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
示例 2：
输入：arr = [2,3,5], target = 10
输出：5
示例 3：
输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361
算法：
一、二分查找
class Solution {
public:
int check(const vector<int>& arr, int x) {//计算value = x 的时候，数组的总和
int ret = 0;
for (const int& num: arr) {
ret += (num >= x ? x : num);
}
return ret;
}
int findBestValue(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());
int n = arr.size();
vector<int> prefix(n + 1);
for (int i = 1; i <= n; ++i) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}//前缀和存储减少重复计算
int l = 0, r = *max_element(arr.begin(), arr.end()), ans = -1;//r为排序后的数组的最大值
//l为0
//在数组中二分查找出 value = mid 时数组和最接近且不大于taget的ans = mid
while (l <= r) {
int mid = (l + r) / 2;//mid为中间值
auto iter = lower_bound(arr.begin(), arr.end(), mid);//二分查找出数值为mid的第一个位置
int cur = prefix[iter - arr.begin()] + (arr.end() - iter) * mid;//计算数组和
if (cur <= target) {//如果数组和小于target，左边界l右移
ans = mid;
l = mid + 1;
}
else {//如果数组和大于target，右边界l左移
r = mid - 1;
}
}
int choose_small = check(arr, ans);//最接近且不大于taget
int choose_big = check(arr, ans + 1);//最接近且不小于taget
return abs(choose_small - target) <= abs(choose_big - target) ? ans : ans + 1;
}
};二、数学法
class Solution {
public:
int findBestValue(vector<int>& arr, int target) {
int size=arr.size();
//输入异常情况
if(size==0)
return 0;
//排序
sort(arr.begin(),arr.end());
for(int i=0;i<size;++i)
{
//对当前目标数target求size-i个元素的最接近平均整数
double t=(double)target/(size-i);
int m=t;
//四舍五入
if(t-m-0.5>0)
++m;
//如果最小值大于当前平均值
if(arr[i]>=m)
return m;
else
//更新数据
target-=arr[i];
}
return arr[size-1];
}
}c++二分查找函数
头文件： #include <algorithm>
二分查找的函数有 3 个： 参考：C++ lower_bound 和upper_bound
lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个 出现的位置。
upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 最后一个 出现的位置。
binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。
1 函数lower_bound() 参考：有关lower_bound()函数的使用
功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置.
注意：如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！
2 函数upper_bound()
功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置
注意：返回查找元素的最后一个可安插位置，也就是“元素值>查找值”的第一个元素的位置。同样，如果val大于数组中全部元素，返回的是last。(注意：数组下标越界)
PS：
lower_bound(val):返回容器中第一个值【大于或等于】val的元素的iterator位置。
upper_bound(val): 返回容器中第一个值【大于】
