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

🍓🫐🍅本文已收录至：C语言题解系列_Yohifo的博客-CSDN博客

更多题解在此专栏中！

🍉前言

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

题目如下：

题目地址（牛客网）：
数字在升序数组中出现的次数_牛客题霸_牛客网 (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;
}

通过所有示例

这个运行时间和占用内存比较玄学

🍉总结

** 简单来说，我们就是先折半聚拢，然后分开扩散查找的思想，当然这得建立在数组有序的情况下，因此我使用了快排，但事实是不用快排也能运行，可以猜出牛客网中的例子应该都是有序的，总的来说知识点不多，无非就是分支与循环、函数、数组，然后再利用折半+遍历，就能解决这个问题，简单标签当之无愧。**

** 当然这只是我的一种方法而已，如果你能学到知识，那么这篇文章就值了，关于这题肯定有更好的解法供大家学习，希望大家都能找到属于自己的解法！**

** 如果你觉得本文写的还不错的话，期待留下一个小小的赞👍，你的支持是我分享的最大动力！**

** 如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正！**

相关文章推荐

C语言进阶——指针进阶_Yohifo的博客-CSDN博客

C语言初阶——分支与循环_Yohifo的博客-CSDN博客

C语言初阶——函数_Yohifo的博客-CSDN博客

C语言初阶——数组_Yohifo的博客-CSDN博客