首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[剑指offer] 数字在排序数组中出现的次数

[剑指offer] 数字在排序数组中出现的次数

作者头像
尾尾部落
发布2018-09-04 15:00:12
5540
发布2018-09-04 15:00:12
举报
文章被收录于专栏:尾尾部落尾尾部落
题目描述

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

解题思路

正常的思路就是二分查找了,我们用递归的方法实现了查找k第一次出现的下标,用循环的方法实现了查找k最后一次出现的下标。 除此之外,还有另一种奇妙的思路,因为data中都是整数,所以我们不用搜索k的两个位置,而是直接搜索k-0.5和k+0.5这两个数应该插入的位置,然后相减即可。

参考代码

法一:

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int len = array.length;
        if(len == 0)
            return 0;
        int first = getFirst(array, k, 0, len-1);
        int last = getLast(array, k, 0, len-1);
        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }

    public int getFirst(int [] array, int k, int start, int end){
        int mid;
        while(start <= end){
            mid = start + (end - start) / 2;
            if(k <= array[mid])
                end = mid - 1;
            else
                start = mid + 1;
        }
        if(start < array.length && array[start] == k)
            return start;
        else
            return -1;
    }
    // 循环
    public int getLast(int [] array, int k, int start, int end){
        int mid;
        while(start <= end){
            mid = start + (end - start) / 2;
            if(k >= array[mid])
                start = mid + 1;
            else
                end = mid - 1;
        }
        if(end >= 0 && array[end] == k)
            return end;
        else
            return -1;
    }
}

法二:

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return biSearch(array, k+0.5) - biSearch(array, k-0.5);
    }
    public int biSearch(int [] array, double k){
        int start  = 0, end = array.length - 1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(array[mid] > k){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 解题思路
  • 参考代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档