代码编织梦想

题目描述

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

题目链接: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) {
        int mid = (nums.length - 1)>>1;
        int count = 0, l = 0,r = nums.length - 1;
        do{
            if(nums[mid] > target) {
                r = mid;
                mid = (mid + l)>>1;
            }
            else if(nums[mid] < target) {
                l = mid;
                mid = (mid + r)>>1;
            }
        } while(nums[mid] != target);
        int i = mid;
        while(nums[i] == target){
            count++;
            i++;
        }
        while(nums[mid-1] == target){
            count++;
            mid--;
        }
        return count;
    }
}

优化

class Solution {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int mid = (i + j) / 2;
            if(nums[mid] <= target) i = mid + 1;
            else j = mid - 1;
        }
        int right = i;
        i = 0; j = nums.length - 1;
        while(i <= j){
            int mid = (i + j) / 2;
            if(nums[mid] < target) i = mid + 1;
            else j = mid - 1;
        }
        int left = j;
        return right - left - 1;

    }
}

优化题解

只要找到大于这个数的第一个的下标和小于这个数的第一个下标即可。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45598111/article/details/117374517

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 =

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

在排序数组中查找数字 做题博客链接题目链接描述示例初始代码模板代码 做题博客链接 https://blog.csdn.net/qq_43349112/article/details/108542248 题目链接 https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zha

每日一题:剑指 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(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