升序数组中求一个key出现的次数

本文主要是介绍升序数组中求一个key出现的次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法思路： 在排好序的数组，相同的数字是排列在一起的，所以只需要找到key的左边界和右边界即可。

找左边界可以看成是找数组中第一个大于等于key的数的位置，找右边界可以看成是找最后一个小于等于key的数。

复杂度分析：时间复杂度是O(log(n))，空间复杂度是O(n)。

 

#include <stdio.h>
/** @brief 在升序数组a中找到第一个大于等于key的数的位置,如果不存在这样的位置，例如* 数组a中所有的数字都比key小，则返回的数是n* @parma int* a 升序数组* @parma int n  数组a的长度* @int key 待查找的关键字*/
int find_left(int* a, int n, int key){int l, r, mid; l = 0; r = n-1;while(l <= r){int mid = (l+r) >> 1; if(a[mid] >= key) r=mid-1; else l=mid+1; }return r+1; 
}/** @brief 在升序数组a中找到最后一个小于等于key的数的位置,如果不存在这样的位置，例如* 数组a中所有的数字都比key大，则返回的数是-1* @parma int* a 升序数组* @parma int n  数组a的长度* @int key 待查找的关键字*/
int find_right(int* a, int n, int key){int l, r, mid; l = 0; r = n-1;while(l <= r){int mid = (l+r)>>1; if(a[mid] <= key) l = mid + 1; else r = mid - 1; }    return l-1; 
}
int count(int* a, int n, int key){int l = find_left(a, n, key);int r = find_right(a, n, key);int cnt = r-l+1; return cnt; 
}
int main(){//输入和输出重定向freopen("in.txt","r", stdin);freopen("out.txt", "w", stdout);const int N = 4; int a[N] = {2, 4, 4, 5}, key; //use case 1：key比数组中所有的数都要小key = 1; printf("%d出现的次数是%d\n", key, count(a, N, key));//use case 2：key在数组出现了一次key = 2; printf("%d出现的次数是%d\n", key, count(a, N, key));//use case 3：key在数组出现了不止一次key = 4; printf("%d出现的次数是%d\n", key, count(a, N, key));//use case 4：key不在数组中，但大于数组中的最小数，小于数组中的最大数key = 3; printf("%d出现的次数是%d\n", key, count(a, N, key));//use case 5：key比数组中的最大数还大key = 6; printf("%d出现的次数是%d\n", key, count(a, N, key));return 0; 
}

 输出结果如下：

1出现的次数是0

2出现的次数是1

4出现的次数是2

3出现的次数是0

6出现的次数是0

 

这篇关于升序数组中求一个key出现的次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---