数组 + 区间
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): 返回容器中第一个值【大于】