代码编织梦想

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

示例 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

思路:
二分,同[leetcode]34.在排序数组中查找元素的第一个和最后一个位置,lower_bound与upper_bound的写法。
注意特殊情况的处理,特殊情况比较多。

AC代码:(C++)

class Solution {
   public:
    int upper_bound(vector<int>& nums, int target) {
        //第一个大于target的元素
        int left = 0, right = nums.size() - 1, mid;
        while (left < right) {
            mid = (right - left) / 2 + left;
            if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    int lower_bound(vector<int>& nums, int target) {
        //第一个大于等于target的元素
        int left = 0, right = nums.size() - 1, mid;
        while (left < right) {
            mid = (right - left) / 2 + left;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;  //nums为空
        if (nums.size() == 1) {
            //nums中只有一个元素,判断这个元素是不是等于target
            return nums[0] == target ? 1 : 0;
        }
        int left = lower_bound(nums, target);
        int right = upper_bound(nums, target);
        if (nums[left] != target) {
            //此时nums中不存在target
            return 0;
        }
        if (nums[right] == target) {
            //target为nums中最大的元素,不存在第一个大于target的元素,于是减完要加一
            return right - left + 1;
        } else {
            return right - left;
        }
    }
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44699689/article/details/120812224

LeetCode(剑指offer-Array)-面试题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 链接:https://leetcode-c

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

题目难度: 简单 原题链接 今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了 题目描述 统计一个数字在排序数组中出现的次数。 0 <= 数组长度 <= 5

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

from typing import List class Solution: def search(self, nums: List[int], target: int) -> int: if not nums: return 0 l, r = 0, len(nums)-1

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. 在排序数组中查找数字-爱代码爱编程

故心故心故心故心小故冲啊 文章目录 题目:统计一个数字在排序数组中出现的次数。解法一:暴力破解过滤filter 题目:统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target =

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

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

剑指 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

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

难度:简单。 标签:数组,二分查找。 使用二分法查找第一个大于等于target的数。 正确解法: class Solution { public: int search(vector<int>& nums, int target) { int n = nums.size(); int lef

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

题目描述 统计一个数字在排序数组中出现的次数。 题目链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 最初的想法 class Solution { public int search(int[] nums, int target

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

 原题链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/ 题意: 统计一个数字在排序数组中出现的次数。  方法一:简单的判断逻辑 class Solution { public: int search(vecto

LeetCode 剑指 Offer 53 - I. 在排序数组中查找数字 I [java实现]-爱代码爱编程

一、问题描述 统计一个数字在排序数组中出现的次数。   二、测试数据 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 提示: 0 <= 数组长度 <= 50000  

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

题目:思路1: 第一想到的应该就是暴力求解了,设置计数器,遍历数组,如果遇到与target相同的数字,就让计数器+1,最后return 计数器即可。 代码如下: # 最简单的 直接遍历 时间复杂度为O(n) class Solution: def search(self, nums: List[int], target: int) ->

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 //题意本为用二分查找 public static int Search(in

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

JavaScript——leetcode剑指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 代

leetcode55.跳跃游戏——学习笔记-爱代码爱编程

题目:力扣https://leetcode-cn.com/problems/jump-game/ class Solution { public boolean canJump(int[] nums) { int except = 0; for(int i=0;i<nums.length;i++){

剑指offer 64.68Ⅰ.68Ⅱ. 搜索与回溯算法(中等)-爱代码爱编程

64. 题目: 剑指 Offer 64. 求1+2+…+nhttps://leetcode-cn.com/problems/qiu-12n-lcof/ 想法:使用递归.但是终止递归需要if,能不能不用if? -> 使用&&短路 代码: class Solution { public int sumNums(int

leetcode236. 二叉树的最近公共祖先-爱代码爱编程

1.题目描述: 给定一个二叉树,找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为:对于有根树T的两个节点p、q,最近公共祖先表示为一个节点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。 2.路径法(存储父节点信息): 看完题目发现递归一下写不出,于是想找出p、q的遍历路径:5—>3,4—>2—&