代码编织梦想

题目链接剑指 Offer 53 - I. 在排序数组中查找数字 I
题目

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

注意:本题与主站 34. 在排序数组中查找元素的第一个和最后一个位置相同(仅返回值不同),34题题解见:力扣:34. 在排序数组中查找元素的第一个和最后一个位置

思路和算法
在这题中,主要关注的点是这个数组是排序数组。那么,虽然双指针能完成查找符合的区间,但是时间复杂度为O(n),并且也没有用上题中给的排序这个条件。显然这个时候用二分查找会比较快,并且时间复杂度也仅为O(nlog n)。
寻找区间左边界和右边界,用的二分查找有部分代码不一样,但是大部分都是可以复用的,这时就可以将代码拿出来单独写,复用代码条件需要加上一个标记(flag)来区分是寻找左边界还是右边界。
代码(c++)

//二分查找:左闭右开区间
class Solution {
public:
    //抽出可复用的代码
    //flag标记是寻找左边界还是右边界
    int binarySearch(vector<int>& nums, int target, bool flag) {
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target || (flag && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return ans;
    }

    int search(vector<int>& nums, int target) {
        //寻找与目标值相等的左边界
        int leftIndex = binarySearch(nums, target, true);
        //寻找大于目标值的最小右边界
        int rightIndex = binarySearch(nums, target, false);
        if (leftIndex < rightIndex && rightIndex <= nums.size() && nums[leftIndex] == target && nums[rightIndex - 1] == target) {
            return rightIndex - leftIndex;  //返回等于目标值的区间
        }
        return 0;   //不存在则返回 0
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_46111138/article/details/124468522

【Java语言】力扣系列----剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <= 数组长度 <= 50000 具体代码实现如下: class Solution

LeetCode:剑指 Offer 53 - I. 在排序数组中查找数字 I(C语言)-爱代码爱编程

题目描述: 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <= 数组长度 <= 50000 作者:Krahets 链接:http

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(LeetCode)-爱代码爱编程

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(LeetCode) 题目描述 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制:

剑指 Offer 53 - I. 在排序数组中查找数字 I的hashmap解法(JavaScript)-爱代码爱编程

一、题目描述 统计一个数字在排序数组中出现的次数。 直达链接是https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 二、示例 三、解题思路 其实看到是排好序的数组的话第一个思路是二分法,但是自己对于hash比较熟悉就用了这个方法 四、代码

剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

剑指 Offer 53 - I. 在排序数组中查找数字 I 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <= 数组长度 <= 5

力扣 剑指 Offer 53 - I. 在排序数组中查找数字 I(简单)-爱代码爱编程

题目 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <= 数组长度 <= 50000题解 二分法+线性扫描 找到target首次

力扣 剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

题目来源:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 大致题意: 统计一个数字在排序后(升序)数组中出现的次数。 思路 二分查找 排序后的数组,查找元素肯定是二分。 既然找次数,那就改变二分的优先级。 对比时先判断当前位置元素是否大于

力扣 [简单] [剑指 Offer 53 - I. 在排序数组中查找数字 I](待补充二分法)-爱代码爱编程

剑指 Offer 53 - I. 在排序数组中查找数字 I 难度简单153收藏分享切换为英文接收动态反馈 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

力扣题解:剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

题目 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 解题思路 有题目可以,nums是一个非递减数组 一次遍历数组,时间复杂度O(n) 当nums[i] == target,出现次数+1nums[i] > target,结束循环二分查找,

剑指 Offer 53 - I. 在排序数组中查找数字-爱代码爱编程

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(LeetCode) (leetcode-cn.com) 首先放上运行结果 思路 所有的查找都是二分查找。首先查找到一个target出现的位置,然后再在这个位置之前找到target首次出现的位置的前一个位置,然后再在这个位置之后找到target最后一次出现的位置,两个位置之差即为

79. 单词搜索-爱代码爱编程

原题链接:79. 单词搜索   solution:         dfs+回溯 class Solution { public: int m,n,length; vector<vector<char>> c_board; string c_word; int dx[4] = {-1,0,1,

JZ26 树的子结构-爱代码爱编程

题目链接:树的子结构_牛客题霸_牛客网 注意点: 1.先在树A中找到值为树B根节点的值的节点,然后判断这个节点的子树是否含有和树B一样的结构。 第一步中,查找与根节点值一样的节点,采用递归的方法来遍历树。第二步中,同样采用递归的方法,判断判断当前对应节点是否相同,然后递归判断左、右节点,递归终止条件是到达了叶节点。2.原书解法为递归的思想,我

【leetcode】字符串解码-爱代码爱编程

Solution 1,辅助堆栈 费了好大的力气搞明白算法的逻辑了,代码不够简洁,在下一部分继续优化 class Solution(object): def decodeString(self, s): """ :type s: str :rtype: str """

【字符串专题】—— 翻转字符串与其子串-爱代码爱编程

LeetCode 151: 颠倒字符串中的单词 ⭕️ 解题思路: (水一篇博客) 去除字符串中多余的空格:字符串前面、字符串后面,字符串中单词之间只保留一个空格 class Solution { public String reverseWords(String s) { //去除重复空格 Stri

再战leetcode (299.猜数字游戏)-爱代码爱编程

299.猜数字游戏 题目描述 题解 我们首先先计算公牛的数目,再计算奶牛的数目。 公牛的数目: 就是相同字符的数目奶牛的数目: 在这个位置上字符但是不想等,secret有这个字符代码 class Solution { public String getHint(String secret, String guess) {

【剑指 offer 53 -爱代码爱编程

【剑指 Offer 53 - I. 在排序数组中查找数字 I】 题目描述:示例:解析思路1:遍历+计数代码(python3)代码(cpp) 解析思路2:二分法查找代码(python3)代码(cpp)

二叉树进阶相关题目-爱代码爱编程

1.606. 根据二叉树创建字符串 根据题目描述,当右子树为空的情况括号要省略,左子树为空不能省略 class Solution { public: void _tree2str(TreeNode*root, string &s) { if(root == nullptr) return;