剑指Offer 第53题：数字在升序数组中出现的次数

北海

发布于 2023-07-01 10:51:45

1610

发布于 2023-07-01 10:51:45

文章被收录于专栏：用户10155340的专栏

🍉前言

我们题解系列话不多说，直接来看题目就行。

题目如下：

题目地址（牛客网）：数字在升序数组中出现的次数_牛客题霸_牛客网 (nowcoder.com)

作为剑指系列算法第一题，牛客网给的标签是简单，但通过率比较低，其实这题真不难，我们可以在二分查找的基础上进行改动，能够很好的解决这个题。

🍉正文

🍍思路分析部分

解题思路：首先二分查找，迅速找到目标数字，然后再把此时的移动距离同时赋给左与右，让它们向两边进行展开比对即可，当然计数器也会进行记录。虽然题目说了是非降序数组，但也有可能数组是乱序的，因此我们首先会对数组进行快排（二分查找十分依赖有序），经过我的测试发现，不使用快排也能通过，当然加上保险些。

🍍具体代码分析部分

大题思路就是这样，下面我们来看看代码实现

qsort快排： C语言进阶——指针进阶_Yohifo的博客-CSDN博客

🍍原码展示

下面是原码展示：

#include<stdlib.h>
int cmp(const void*e1,const void*e2)
{
    return *(int*)e1 - *(int*)e2;//快排判断函数
}
int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    qsort(data,dataLen,sizeof(*data),cmp);
    if(k > *(data+dataLen-1) || dataLen == 0)
    {
        return 0;//排除目标数大于数组最大值及数组长度为0的情况
    }
    int count = 0;//计数器
    int left = 0;//左辅助偏移值
    int right = dataLen - 1;//右辅助偏移值
    while(left < right)
      {
          //二分查找部分
          int mid = (left + right) / 2;//中间值每次都会变化
          if(*(data + mid) < k)
          {
              left = mid + 1;//左往右移动
          }
          if(*(data + mid) > k)
          {
              right = mid - 1;//右往左移动
          }
          if(*(data + mid) == k)
          {
              left = mid;//赋值
              right = mid;//赋值
              break;//结束循环
          }
      }
    while(*(data + left) == k)
    {
        count++;//计数器++
        left--;//左偏移值--
    }
    while(*(data + right) == k)
    {
        count++;//计数器++
        right++;//右偏移量++
    }
    if(count)
    {
        //排除不存在目标数的情况
        return count - 1;//减去重复数
    }
    return 0;
}