php做网站模板,北京百度竞价,wordpress免费教程视频,wordpress两个域名访问题目
LCR 172. 统计目标成绩的出现次数 某班级考试成绩按非严格递增顺序记录于整数数组 scores#xff0c;请返回目标成绩 target 的出现次数。 示例 1#xff1a; 输入#xff1a;scores [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target 4 输出#xff1a;3 示例 2#xff1a…题目
LCR 172. 统计目标成绩的出现次数 某班级考试成绩按非严格递增顺序记录于整数数组 scores请返回目标成绩 target 的出现次数。 示例 1 输入scores [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target 4 输出3 示例 2 输入scores [1, 2, 3, 5, 7, 9], target 6 输出0 提示0 scores.length 105-109 scores[i] 109scores 是一个非递减数组-109 target 109 注意本题与主站 34 题相同仅返回值不同https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 解法1哈希表直接统计出现次数
class Solution {
public:int countTarget(vectorint scores, int target) {mapint, int m;for(auto ele:scores) m[ele];return m[target] ? m[target] : 0;}
};解法2二分查找边界
如果使用哈希表进行统计需要遍历整个数组时间复杂度是 O(n)且并没有用到数组是非递减序列这个条件注意到非递减序列如果目标值在数组中出现则一定是连续出现的那么只需要找到其上下边界即可上下边界的查找可以使用二分法此时不需要遍历整个序列时间复杂度小于 O(n)此处的二分查找为常规二分查找的变形如果目标节点在序列中返回的是右开的上界如果目标节点不在序列中那么则返回目标节点该有的插入位置所以如果要找 target 左边的边界则对 target-1 进行寻找即可此处的二分查找如何编写其实就是将常规的二分查找的 nums[middle]target 合并到 tarnums[middle] 这种情况中随便选一种合并即可 class Solution {
public:int findBound(vectorint nums, int tar){int left0, rightnums.size()-1;while(leftright){int middleleft(right-left)/2;if(tarnums[middle]) leftmiddle1;else rightmiddle-1;}return left;}int countTarget(vectorint scores, int target) {return findBound(scores, target) - findBound(scores, target-1);}
};解法3利用 STL 内置的边界查找函数
upper_bound() 寻找有序序列大于 target 的第一个最小的元素lower_bound() 寻找有序序列第一个等于 target 的元素 class Solution {
public:int countTarget(vectorint scores, int target) {return upper_bound(scores.begin(), scores.end(), target) - lower_bound(scores.begin(), scores.end(), target);}
};
