菜鸟笔记
提升您的技术认知

数字在排序数组中出现的次数-ag真人游戏

阅读 : 327

题目:
统计一个数字在排序数组中出现的次数,比如排序数组为{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一定在右半边:
![数字在排序数组中出现的次数](https://static.coonote.com/51b875c75cb51231e533e957b957e3aa.png)

如果中间数字右侧相邻的数不是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)
网站地图