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

题目: 统计一个数字在排序数组中出现的次数,比如排序数组为{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 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

2729
来自专栏androidBlog

二分查找的相关算法题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

421
来自专栏Coding迪斯尼

在未知长度的超大数组中线性时间内查找第k大的元素

给定一个长度为n的数组,n是一个很大的值,而且事先不知道n的大小,给定一个确定的数值k,要求设计一个找出数组中第k大的元素,要求算法需要的空间不能超过O(k)。

822
来自专栏Linux驱动

快速排序(详解)

描述: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序...

1819
来自专栏余林丰

4.比较排序之归并排序(递归)

  归并排序里运用到算法里很重要的一个思想——分治法:将原问题分解为几个规模较小但类似于原问题的子问题——《算法导论》。在每一层递归中都有3个步骤:   1.分...

1778
来自专栏算法与数据结构

数据结构 数组和广义表以及树的基本概念

2-1 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分) 1...

1778
来自专栏Python小屋

Python高级数组处理模块numpy用法精要

numpy是Python的高级数组处理扩展库,提供了Python中没有的数组对象,支持N维数组运算、处理大型矩阵、成熟的广播函数库、矢量运算、线性代数、傅里叶变...

2777
来自专栏开发 & 算法杂谈

序列中查找第二小元素

序列中查找第二小元素有很多方法,本文介绍的是采用分治的思想,自底向上,序列中两两构成一对,比较选出最小值,然后构成上一层序列,然后依次网上构造,最后,根节点就是...

653
来自专栏欧阳大哥的轮子

常见排列组合问题的计算公式

在进行排列组合计算以及概率计算时我们经常会遇到一些具有相同性质的问题。假设问题的样本空间Ω中一共有k种类型的元素α, β,γ... κ。每种类型的元素个数分别为...

812
来自专栏Python数据科学

99%的人都不知道的pandas骚操作(一)

pandas有一种功能非常强大的方法,它就是accessor,可以将它理解为一种属性接口,通过它可以获得额外的方法。其实这样说还是很笼统,下面我们通过代码和实例...

1102

扫码关注云+社区