算法-数字在排序数组中出现的次数

题目: 统计一个数字在排序数组中出现的次数,比如排序数组为{1,2,3,3,3,4,5},那么数字3出现的次数就是3。

解题思路: 1.首先,遍历数组肯定就能知道某个数字的个数,此时的时间复杂度O(n)。 2.除此之外,我们注意到,任务本质上是查找问题,而且是排序好数组,可以尝试用二分查找算法,这样我们可以找到一个3,然后根据这个3向数组的两端遍历,找到所有的3,但是如果3是n个呢?这个算法本质上时间复杂度还是O(n)。 3.最后,我们发现在排序数组中,如果我们知道了第一个3和最后一个3出现的位置,那么其实也就知道了个数,那么我们能否在第一次使用二分查找之后,继续使用二分法,找到两端的3? 显然可以的,只不过不要稍微修改一些传统二分查找的规则: 如果中间的数字大于3,那么第一个和最后一个3肯定在左半边;

如果中间的数字小于3,那么第一个和最后一个3肯定在右半边;

如果中间的数字等于3,那么需要判断这个3是不是第一个或最后一个3: 如果中间数字左侧相邻的数是3,那么第一个3一定在左半边:

如果中间数字左侧相邻的数不是3,那么第一个3就在中间:

如果中间数字右侧相邻的数是3,那么最后一个3一定在右半边:

如果中间数字右侧相邻的数不是3,那么最后一个3一定就在中间:

所以,我们可以把找第一个和最后一个分成两个问题来考虑,用两个函数分别返回在数组中的位置,那么他们的差值+1就是个数。

个人感觉,二分查找的关键在于用一种规则,让每次查找之后的范围都可以减半,一次来降低时间复杂度,所以改进的二分查找可以很多问题中灵活使用,除了这个,在旋转数组的最小数字问题中也可以用到,甚至在旋转数组的最小数字中,连二分查找的前提条件都变了,不再是一个顺序的数组。

代码实现

int GetNumberOfK(int* data, int length, int k)
{
    int number = 0;

    if(data != NULL && length > 0)
    {
        int first = GetFirstK(data, length, k, 0, length - 1);
        int last = GetLastK(data, length, k, 0, length - 1);

        if(first > -1 && last > -1)
            number = last - first + 1;
    }

    return number;
}
//找第一个k
int GetFirstK(int* data, int length, int k, int start, int end)
{
    if(start > end)
        return -1;

    int middleIndex = (start + end) / 2;
    int middleData = data[middleIndex];

    if(middleData == k)
    {
        if((middleIndex > 0 && data[middleIndex - 1] != k) 
            || middleIndex == 0)
            return middleIndex;
        else
            end  = middleIndex - 1;
    }
    else if(middleData > k)
        end = middleIndex - 1;
    else
        start = middleIndex + 1;

    return GetFirstK(data, length, k, start, end);
}
//找最后一个k
int GetLastK(int* data, int length, int k, int start, int end)
{
    if(start > end)
        return -1;

    int middleIndex = (start + end) / 2;
    int middleData = data[middleIndex];

    if(middleData == k)
    {
        if((middleIndex < length - 1 && data[middleIndex + 1] != k) 
            || middleIndex == length - 1)
            return middleIndex;
        else
            start  = middleIndex + 1;
    }
    else if(middleData < k)
        start = middleIndex + 1;
    else
        end = middleIndex - 1;

    return GetLastK(data, length, k, start, end);
}

GetNumberOfK函数没啥好说的,就是在调用,剩下的GetFirstKGetLastK逻辑是一样的,只要理解一个就好了。 在GetFirstK中,使用了递归的方法,在下一次递归前,一直在调整数组范围,让下一次递归与本次递归相比,范围少了一半,这就是二分。 递归退出的条件就是:

if((middleIndex > 0 && data[middleIndex - 1] != k) 
            || middleIndex == 0)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

第7章 集合类第7章 集合类

在 Java 类库中有一套相当完整的容器集合类来持有对象。Kotlin没有去重复造轮子(Scala则是自己实现了一套集合类框架),而是在Java 类库的基础上进...

822
来自专栏黑泽君的专栏

自定义异常的实现和测试以及异常的注意事项

/* * java不可能对所有的情况都考虑到,所以,在实际的开发中,我们可能需要自定义异常类。 * 而我们自己随意的写一个类,是不能作为自定义异常类来看待的...

5641
来自专栏Phoenix的Android之旅

Java面试的基础中的基础

面试时经常从Java的基础知识开始,最基础的部分莫过于Java的集合类型。我们知道Java的集合类型有三种,Set,List,Map,那这三种有什么区别呢。

1011
来自专栏java学习

Java每日一练(2017/8/17)

每日一句 学的到东西的事情是锻炼,学不到的是磨练。 查看以前的所有练习题目以及答案:https://mp.weixin.qq.com/mp/homepage?_...

2929
来自专栏desperate633

LintCode 最长上升连续子序列题目样例分析1(普通解法)分析2(使用队列)

给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列...

872
来自专栏Android先生

Kotlin的高阶函数和常用高阶函数

首先我们可以知道, forEach 是 Array 的扩展函数,然后参数是 action ,但是 action 不再像和我们以前Java那样传递的是一个对象,这...

1581
来自专栏用户3030674的专栏

java集合的操作(set,Iterator)

Iterator、Collection、Set和HashSet关系  Iterator<——Collection<——Set<——HashSet  Iterat...

2893
来自专栏null的专栏

python基础知识——内置数据结构(集合)

python中的set是指一系列无序元素的集合,其中的元素都是相异的,常见的操作包括集合的并集,交集和补集等操作。 1、set的创建 格式 set_name =...

3467
来自专栏Ryan Miao

java中List对象列表去重或取出以及排序

面试碰到几次list的去重和排序。下面介绍一种做法: 1. list去重 1.1 实体类Student List<Student>容量10k以上,要求去重复。这...

8189
来自专栏lgp20151222

java中两个map比较

1352

扫码关注云+社区

领取腾讯云代金券