专栏首页猿计划剑指Offer LeetCode 面试题53 - I. 在排序数组中查找数字 I

剑指Offer LeetCode 面试题53 - I. 在排序数组中查找数字 I

面试题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

简单暴力解法

class Solution {
    public int search(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                sum++;
            }
        }
        return sum;
    }
}

二分查找

因为数组是已经排序好的数组,所以可以先找出左右边界,找到数组中的左右边界,然后相减就可以拿到这个数字了.

/**
 * @Auther: truedei
 * @Date: 2020 /20-5-20 08:45
 * @Description:
 */
public class Test1 {

    static  public int search(int[] nums, int target) {


        int i=0;
        int j=nums.length-1;
        int left=0,right=0;

        //搜索左边界
        while (i<=j){
            int mid =  (i + j) /2;

            if(nums[mid] <= target)
                i = i + 1;
            else
                j = j - 1;
        }

        right = i;

        i = 0;
        j=nums.length-1;

        //搜索右边界
        while (i<=j){
            int mid =  (i + j) /2;

            if(nums[mid] < target)
                i = i + 1;
            else
                j = j - 1;
        }

        left=j;

        return right - left - 1;
    }

    public static void main(String[] args) {
        int nums[] = new int[]{5,7,7,8,8,10},target = 8;


        System.out.println(search(nums,target));
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer LeetCode 面试题53 - II. 0~n-1中缺失的数字

    一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个...

    TrueDei
  • 剑指Offer LeetCode 面试题59 - I. 滑动窗口的最大

    输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:

    TrueDei
  • 剑指Offer 面试题03. 数组中重复的数字

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-sh...

    TrueDei
  • Leetcode算法【34在排序数组中查找元素】

    在之前ARTS打卡中,我每次都把算法、英文文档、技巧都写在一个文章里,这样对我的帮助是挺大的,但是可能给读者来说,一下子有这么多的输入,还是需要长时间的消化。

    程序员小跃
  • Leetcode-Solutions 1.two-sum (Python&Golang)

    恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

    小歪
  • LeetCode67|二分查找

    给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则...

    后端Coder
  • 每日算法题——两数之和

    许久不见,终于开始在公司上班了,有一点不好的就是一整天都要戴着口罩,闷得慌,不知道大伙儿有没有这种感觉。

    用户2802329
  • 【leetcode刷题】20T1-两数之和

    https://leetcode-cn.com/problems/two-sum/

    木又AI帮
  • LeetCode68|和为s的两个数字

    双指针的使用,最近一段时间的输出文章都是自己之前做过的内容,自己打算将做过的题都整理成一篇篇文章进行梳理一下,喜欢看java的文章可以查看历史记录,本人写过My...

    后端Coder
  • Leetcode#1.Two Sum(两数之和)

    题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

    武培轩

扫码关注云+社区

领取腾讯云代金券