网站建设动态静态,山西企业网站建设,互联网推广公司排名,域名申请后怎么建网站原题链接
难度#xff1a;easy\color{Green}{easy}easy 题目描述
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums [5,7,7,8,8,10], target 8
输出: 2示例 2:
输入: nums [5,7,7,8,8,10], target 6
输出: 0提示#xff1a; 0nums.length1050 …原题链接
难度easy\color{Green}{easy}easy 题目描述
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums [5,7,7,8,8,10], target 8
输出: 2示例 2:
输入: nums [5,7,7,8,8,10], target 6
输出: 0提示
0nums.length1050 nums.length 10^{5}0nums.length105−109nums[i]109-10^{9} nums[i] 10^{9}−109nums[i]109numsnumsnums 是一个非递减数组−109target109-10^{9} target 10^{9}−109target109
注意 本题与主站 34 题相同仅返回值不同https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 面试官出这题的话肯定是想让你写二分的啦 其他没用。 给面试官说有两种类型的解法一种是暴力一种是二分法求边界体现递进的思考过程别上来一言不发写个二分失去一个表现机会。 对于二分法我们可以分别求左边界和右边界也可以二分求左边界之后接着遍历计数两种情况对应在真实场景下连续相等的数据一般有多长。如果经常出现很长一串连续相等的数据就用二分法求右边界否则容易使算法退化到 O(n)。 分析完了之后给一个规范的解法注意函数驼峰式命名这些能体现你专业性的小细节 算法1
(模拟)
创建一个变量 ans扫描整个数组如果数组中的值等于 target那么 ans 就加一最后输出答案。
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是数组的长度。需要遍历数组一次。 空间复杂度 : O(1)O(1)O(1)只需要常数空间存放若干变量。
C 代码
class Solution {
public:int search(vectorint nums, int target) {int ans 0;for (int i 0; i nums.size(); i ) {if (nums[i] target)ans ;}return ans;}
};算法2
(二分) 排序数组 nums 中的所有数字 target 形成一个窗口记窗口的 左 / 右边界 索引分别为 left 和 right 分别对应窗口左边 / 右边的首个元素。 本题要求统计数字 target 的出现次数可转化为使用二分法分别找到 左边界 left 和 右边界 right 易得数字 target 的数量为 right−left−1 。 复杂度分析 时间复杂度O(logn)O(logn)O(logn)二分法为对数级别复杂度。 空间复杂度 : O(1)O(1)O(1)几个变量使用常数大小的额外空间。
C 代码
class Solution {
public:int search(vectorint nums, int target) {if (nums.size() 0) return 0;int l 0, r nums.size() - 1;int ans 0;//寻找最左边的下标while (l r) {int mid (l r) / 2;if (nums[mid] target)r mid;else l mid 1;}if (nums[l] ! target) return ans;int left l;l 0, r nums.size() - 1;//寻找右边的下标while (l r) {int mid (l r 1) / 2;if (nums[mid] target)l mid;else r mid - 1;}int right l;ans right - left 1;return ans;}
};
