首页 > 试题广场 >

数字在升序数组中出现的次数

[编程题]数字在升序数组中出现的次数

热度指数：610877 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围： $0 \le n \le 1000 , 0 \le k \le 100$ ，数组中每个元素的值满足 $0 \le val \le 100$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logn)$

示例1

输入

[1,2,3,3,3,3,4,5],3

输出

示例2

输入

[1,3,4,5],6

输出

算法知识视频讲解

路由器_

int GetNumberOfK(int* nums, int numsLen, int k ) {

int count=0;

for (int i=0; i<numsLen; i++) {

if (nums[i]==k) {

count++;

}

return count;

}

发表于 2023-09-05 09:27:57 回复(0)

ChrisBosh

int GetNumberOfK(int* nums, int numsLen, int k ) 
{
    int count=0;
    for (int i=0;i<numsLen;i++)
    {
        if (nums[i]==k)
        count++;
    }
    return count;
}

发表于 2023-08-10 21:59:10 回复(0)

小小小孩

 //1是右边界，0是找左边界
int search_boundary(int direction,int* data, int dataLen, int k )
{   
    int l = 0,r=dataLen-1;
    while(l<=r)
    {
        int mid = (l+r)/2;
        if(direction==1)
        {
            if(data[mid]<=k)
                l=mid+1;
            else
                r=mid-1; 
        }  
        else 
        {
            if(data[mid]>=k)
                r=mid-1; 
            else
                l=mid+1;
        } 
    }
    if(direction==1 && data[r] == k)
        return r+1; //多加一个好算总数
    else if(direction==0 && data[l] == k)
        return l;
    return 0;
}
int GetNumberOfK(int* data, int dataLen, int k ) 
{
    // write code here
   if(data == NULL || dataLen == 0)
        return 0;
    return search_boundary(1,data,dataLen,k)-search_boundary(0,data,dataLen,k);
}

发表于 2023-05-25 14:47:14 回复(0)

80后大叔

时间复杂度O(n)，极限情况下遍历完整的数组

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    if(dataLen==0 || k<data[0] || k>data[dataLen-1]) return 0;
    int left=0,right=dataLen-1;
    while(left <= right && (data[left] != k || data[right] != k)) {
        // printf("left:%d,right:%d\n", left, right);
        int mid = left+(right-left)/2;
        if(data[mid]<k) left=mid+1;
        else if(data[mid]>k) right=mid-1;
        else if(data[mid]==k){
            if(data[left]<k) left++;
            if(data[right]>k) right--;
        }
    }
    return right-left+1;
}

发表于 2022-11-15 11:09:10 回复(0)

人来疯的伊登等一个offer

void Dichotomy_check(int *a,int*count,int key,int left,int right)
{
    if(left>right)
        return;
      int mid=(left+right)/2;
    if(a[mid]>key)//那么一定在左区间，更新区间
    {       right=mid-1;
      Dichotomy_check(a, count,  key,  left, right);
     }
    else if(a[mid]<key)//一定在右区间，更新区间
    {      left=mid+1;
         Dichotomy_check(a, count,  key,  left, right);
    }
    else//左右区间都有可能
    {
        (*count)++;
        Dichotomy_check(a, count,  key,  left, mid-1);
        Dichotomy_check(a, count,  key,  mid+1, right);
    }
    
}
int GetNumberOfK(int* data, int len, int k ) {
    // write code her
    int*count=(int*)malloc(4);//用来记录符合条件的k的次数
    *count=0;
    int left=0;
    int right=len-1;
    Dichotomy_check(data, count, k,  left,  right);//采用分治的思想，分别对左右区间进行查找
    int tmp_count=*count;
    free(count);
    count=NULL;
    return tmp_count;
    
}

发表于 2022-08-28 13:16:49 回复(0)

非科班的小fw

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    int left=0;
    int count=0;
    int right=dataLen-1;
    while(left<=right)
    {
        int mid=(right+left)/2;
       if(data[mid]<k)
            left=mid+1;
       else if(data[mid]>k)
            right=mid-1;
        
       else if(data[mid]==k)
       {
           int start=mid+1;
           count=0;
           //左边
           while(mid>=0&&data[mid]==k)
           {
               count++;
               mid--;
           }
           //右边
           while(start<dataLen&&data[start]==k)
           {
               count++;
               start++;
           }
           break;
       }
    }
    return count;
}

发表于 2022-08-20 01:15:50 回复(0)

牛客750631111号

int GetNumberOfK(int* data, int dataLen, int k ) {
    int left = 0;
    int right = dataLen - 1;
    int count = 0;
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if (data[mid] > k)
            right = mid - 1;
        else if (data[mid] < k)
            left = mid + 1;
        else
        {
            count++;
            //记录找到的位置
            int tmp = mid;
            //从该位置向左找，直到找到不同数
            while(--tmp >= 0 && data[tmp] == k)
            {
                count++;
            }
            tmp = mid;
            //从该位置向右找，直到找到不同数
            while (++tmp < dataLen && data[tmp] == k)
            {
                count++;
            }
            break;
        }
    }
    return count;
}

发表于 2022-07-16 16:13:31 回复(0)

王大可~

/**
 * 
 * @param data int整型一维数组 
 * @param dataLen int data数组长度
 * @param k int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int GetNumberOfK(int* data, int dataLen, int k ) {// write code here
    int n = 0;
    for (int i = 0; i < dataLen; i++)
    {
         if (*(data + i) == k)
         {
             n++;
         }
    }
    return n;
}

发表于 2022-07-13 23:45:58 回复(1)

牛客800396556号

int GetNumberOfK(int* data, int dataLen, int k ) {
    int l=0,r=dataLen-1,mid;
    while(l<=r){
        mid=(l+r)/2;
        if(data[mid]>k) r=mid-1;
        else if(data[mid]<k) l=mid+1;
        else{
            l=mid-1;
            r=mid+1;
            while(l>=0&&data[l]==k) l--;
            while(r<dataLen&&data[r]==k) r++;
            return r-l-1;
        }
    }
    return 0;
}

发表于 2022-03-29 17:45:16 回复(0)

北方留意尘

int find(int*data,int len,int k,int flag)
{
    int left=0,right=len-1,mid;
    while(left<=right){
        mid=left+(right-left)/2;
        if(data[mid]>k)
            right=mid-1;
        else if(data[mid]<k)
            left=mid+1;
        else{
            if(flag==0){//flag==0，找最左边数字，
                if(mid==left ||data[mid-1]!=k) return mid;
                else right=mid-1;//把中心向左推
            }else {
                if(mid==right||data[mid+1]!=k) return mid;
         else left=mid+1;
            }
        }
    }
    return -1;
}

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    if(dataLen==0) return 0;
    int left=find(data,dataLen,k,0);
    int right=find(data,dataLen,k,1);
    if(left==-1&&right==-1) return 0;//没找到
    return right-left+1;
}

发表于 2022-02-17 10:57:59 回复(0)

发炎战士

int find(int* arr,int left,int right,int n)
{
while(left<=right)
{
int mid=(left+right)/2;
if(arr[mid]<n)
{
left=mid+1;
}
else if(arr[mid]>n)
{
right=mid-1;
}
else
{
return mid;
}
}
return -1;
}
int GetNumberOfK(int* data, int dataLen, int k ) {
// write code here
int left=0;
int right=dataLen-1;
int mid=find(data,left,right,k);
if(mid==-1)
{
return 0;
}
int m1=mid;
int m2=mid;
while(m2<dataLen&&data[m2+1]==k)
{
m2=find(data,m2+1,right,k);
}
while(m1>0&&data[m1-1]==k)
{
m1=find(data,left,m1-1,k);
}
return m2-m1+1;
}

发表于 2022-01-25 18:32:12 回复(0)

越努力越幸运_always

int GetNumberOfK(int* data, int dataLen, int k ) {
    // write code here
    int i = 0;
    int j = 0;
    for(i=0;i < dataLen;i++)
    {
        if(*(data+i)==k)
            j++;
    }
    return j;
}

发表于 2022-01-18 09:43:29 回复(0)

赶紧离职

int GetNumberOfK(int* data, int dataLen, int k ) {
// write code here
int i=0,j=0;
for(i=0;i<dataLen;i++){if(k==data[i]){j++;}
}
return j;
}

发表于 2021-11-16 23:36:18 回复(0)

小酷爱

我这种写法不知道算不算是二分查找，设定了left、right两个变量，一个从头向后走一个从尾向前走。

因为这是有序数组，当left或者right等于k时，就能开始数了

int GetNumberOfK(int* data, int dataLen, int k ) {
    int left = 0, right = dataLen-1;
    int count = 0;
    while(left <= right)
    {
        if(data[left] == k)
        {
            left++, count++;
        }
        else if(data[right] == k)
        {
            right--, count++;
        }
        else
        {
            left++, right--;
        }
    }
    return count;
}

发表于 2021-11-08 15:54:01 回复(0)