前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-面试题53-1-在排序数组中查找数字I

LeetCode-面试题53-1-在排序数组中查找数字I

作者头像
benym
发布2022-07-14 15:30:34
5340
发布2022-07-14 15:30:34
举报
文章被收录于专栏:后端知识体系

# LeetCode-面试题53-1-在排序数组中查找数字I

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

示例1:

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例2:

代码语言:javascript
复制
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
  • 限制: 0 <= 数组长度 <= 50000

# 解题思路1

在有序的数组中二分查找,确定第一个k出现的位置和最后一个k出现的位置,然后两个位置相减即是出现次数

# 解题思路2

hash表,遍历的过程中把次数加上去即可,速度慢于2分查找

# Java代码

代码语言:javascript
复制
class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int count = 0;
        if(nums!=null&&len>0){
            int first = GetFristK(nums,len,target,0,len-1);
            int last = GetLastK(nums,len,target,0,len-1);
            if(first>-1&&last>-1){
                count = last-first+1;
            }
        }
        return count;
    }
    public int GetFristK(int[] nums,int len,int target,int start,int end){
        if(start>end)
            return -1;
        int mid = (start+end)/2;
        int midData = nums[mid];
        if(midData==target){
            // 找到第一个k的位置
            if(mid>0&&nums[mid-1]!=target||mid==0)
                return mid;
            else // 如果前面还有k,缩小范围继续找
                end = mid-1;
        }else if(midData>target)
            end = mid-1;
        else
            start = mid+1;
        return GetFristK(nums,len,target,start,end);
    }
    public int GetLastK(int[] nums,int len,int target,int start,int end){
        if(start>end)
            return -1;
        int mid = (start+end)/2;
        int midData = nums[mid];
        if(midData==target){
            // 找到最后一个k的位置
            if(mid<len-1&&nums[mid+1]!=target||mid==len-1)
                return mid;
            else
                start = mid+1;
        }else if(midData<target)
            start = mid+1;
        else
            end = mid-1;
        return GetLastK(nums,len,target,start,end);
    }
}

# Java代码2

代码语言:javascript
复制
class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return 0;
        int left = 0;
        int right = len-1;
        // 通过控制等号控制是左边界还是右边界
        while(left<=right){
            int mid = left+(right-left)/2;
            // 当小于等于target时一直移动左指针
            if(nums[mid]<=target){
                left = mid+1;
            } else { // 当大于target时才移动右指针,这样保障了右指针指向重复target的最后一个位置
                right = mid-1;
            }
        }
        int rightIndex = right;
        left = 0;
        right = len-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            // 当大于等于target时一直移动右指针收缩
            if(nums[mid]>=target){
                right = mid-1;
            } else { // 当小于target时才移动左指针,保障左指针指向重复target的第一个位置
                left = mid+1;
            }
        }
        int leftIndex = left;
        return rightIndex-leftIndex+1;
    }
}

# Java代码3

代码语言:javascript
复制
class Solution {
    public int search(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        return map.containsKey(target)?map.get(target):0;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-05-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • # LeetCode-面试题53-1-在排序数组中查找数字I
    • # 解题思路1
      • # 解题思路2
        • # Java代码
          • # Java代码2
            • # Java代码3
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档