好贷网好贷款

问题5:如何在顺序数组中找到给定数字出现的次数

发布时间:2016-12-3 2:02:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"问题5:如何在顺序数组中找到给定数字出现的次数",主要涉及到问题5:如何在顺序数组中找到给定数字出现的次数方面的内容,对于问题5:如何在顺序数组中找到给定数字出现的次数感兴趣的同学可以参考一下。

      如何在排好序的数组中找到给定数字出现的次数?例如数组[1,2,2,2,3,3]中3出现的次数是2次。     该问题有一个非常容易想到的办法:设定一个计数器count开始为0,然后遍历数组,如果数值为3 则count加1。不过这种办法没有用到该数组是有序数组的条件,不管有序无序都可以用该办法解决, 且时间复杂度为O(n)。     方法一代码如下: #include <stdio.h> int getCount(int a[], int len, int target) { int i, num = 0; for(i=0; i<len; i++) { if(a[i] == target) num++; } return num; } int main(void) { int a[] = {0, 1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 6, 8, 9, 11}; int len = sizeof(a)/sizeof(a[0]); int count = getCount(a, len, 4); printf("%d\n", count); return 0; }    方法二,该数组为有序数组,本方法将尝试利用二分查找法进行改进来获得答案。设数组array为递增序列,需要 查找的元素为findData, 为了求解给定数字出现的次数,可分别寻找findData在array中最先出现的位置和最后出现的位置,然后通过这两者的算术运算即可获得该数字的出现次数。编码的时候,可以用一个变量last来存储本次查找的位置,然后根据情况变换查找方向,就可以分别确定最先出现的位置下标left和最后出现的位置下标right。 代码如下: #include <stdio.h> #include <stdbool.h> //isLeft标记值是否在左边 int binarySearch(int a[], int len, int findData, bool isLeft) { int start = 0; int end = len-1; int last; while(start <= end) { int mid = start+(end-start)/2; if(findData > a[mid]) start = mid + 1; else if(findData < a[mid]) end = mid - 1; else { last = mid; if(isLeft) end = mid-1; else start = mid+1; } } return last>0 ? last : -1; } int main(void) { int a[] = {0, 1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 6, 8, 9, 11}; int len = sizeof(a)/sizeof(a[0]); int Lower = binarySearch(a, len, 4, true); int Upper = binarySearch(a, len, 4, false); int count = Upper - Lower + 1; printf("%d", count); return 0; } 运行结果为: 5

上一篇:构建REST风格的Web Service
下一篇:Java Socket 通过TCP交互 实例

相关文章

相关评论