找出有序元素数组中指定元素出现的次数

题目：

      找出有序数组中指定元素出现的次数，要求时间复杂度为O(lgn)

      ex，

      数组｛0,0,0,2,3,3,3,3,3,4,5,5｝，0出现3次，3出现5次

正如http://blog.csdn.net/yysdsyl/archive/2010/03/26/5419482.aspx所分析，先用二分查找找到指定元素，然后往两边查找的时间复杂度为O(lgn +k)，其中k为查找元素出现的次数，如果次数为n，则该方法不满足要求，因时间复杂度为O(n)。

但是，我们可以先找到大于等于查找元素（即第一次出现，如果出现的话）的索引l，再找到小于等于查找元素（即最后一次出现，如果出现的话）的索引r，两者一减既得所求：r - l + 1

#include <stdio.h> #include <stdlib.h> static int binary_search_first(const int *A, const int n, const int key) { int l = 0, r = n - 1, m = (n - 1) / 2; while (l <= r){ if (A[m] < key) l = m + 1; else r = m - 1; m = (l + r) / 2; } return l; } static int binary_search_last(const int *A, const int n, const int key) { int l = 0, r = n - 1, m = (n - 1) / 2; while (l <= r){ if (A[m] > key) r = m - 1; else l = m + 1; m = (l + r) / 2; } return r; } int main(int argc, char **argv) { const int A[] = {0, 0, 0, 2, 3, 3, 3, 3, 3, 4, 5, 5}; int l, r, key, n; if (argc != 2){ printf("Usage: %s key/n", argv[0]); return 1; } key = atoi(argv[1]); n = sizeof(A) / sizeof(int); /*0 <= l <= n*/ l = binary_search_first(A, n, key); if (l >= n || key != A[l]){ printf("%d not found/n", key); return 0; } /*-1 <= r <= n -1*/ r = binary_search_last(A, n, key); if (l > r){ printf("%d not found/n", key); }else{ printf("%d occurs %d times/n", key, r - l + 1); } return 0; }

最后

以上就是任性黑裤为你收集整理的找出有序元素数组中指定元素出现的次数的全部内容，希望文章能够帮你解决找出有序元素数组中指定元素出现的次数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。