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

题目描述

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

解题思路

正常的思路就是二分查找了,我们用递归的方法实现了查找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;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q67 Add Binary

Given two binary strings, return their sum (also a binary string). For example, ...

2858
来自专栏格子的个人博客

Java源码阅读之LinkedList - JDK1.8

前文基于缓冲数组的ArrayList已经分析过,那么同样作为List实现的LinkedList又有什么不一样呢?

1002
来自专栏计算机视觉与深度学习基础

Leetcode 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string. The expre...

2377
来自专栏专注 Java 基础分享

从源码解析LinkedList集合

     上篇文章我们介绍了ArrayList类的基本的使用及其内部的一些方法的实现原理,但是这种集合类型虽然可以随机访问数据,但是如果需要删除中间的元素就...

2025
来自专栏Java爬坑系列

【Java入门提高篇】Day27 Java容器类详解(九)LinkedList详解

  这次介绍一下List接口的另一个践行者——LinkedList,这是一位集诸多技能于一身的List接口践行者,可谓十八般武艺,样样精通,栈、队列、双端队列、...

933
来自专栏Android研究院

深入理解链表和手写链表以及面试中常问链表的问题

上一期 讲到了 顺序表与链表的基本知识 了解链表的基本知识。并且分析了ArrayList的源码。顺序表(随机访问速度快,插入和删除效率低)和链表(随机访问速度慢...

1.4K2
来自专栏恰童鞋骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

823
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

32212
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

782
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

1443

扫码关注云+社区

领取腾讯云代金券