本文共 2968 字，大约阅读时间需要 9 分钟。
题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1，2，3，3，3，3，4，5}和数字3，由于3在这个数组中出现了4次，因此输出4.
找到排序数组中的第一个K：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | int GetFirstK( int *data, int length, int k, int start, int end) { if (start > end) return -1; int middleIndex = start + ((end - start) >> 1); int middleData = data[middleIndex]; if (middleData == k) { if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0) return middleIndex; else end = middleIndex - 1; } else if (middleData > k) end = middleIndex - 1; else start = middleIndex + 1; return GetFirstK(data, length, k, start, end); } |
找到排序数组中最后一个k：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | int GetLastK( int *data, int length, int k, int start, int end) { if (start > end) return -1; int middleIndex = start + ((end - start) >> 1); int middleData = data[middleIndex]; if (middleData == k) { if ((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length -1) return middleIndex; else start = middleIndex + 1; } else if (middleData < k) start = middleIndex + 1; else end = middleIndex - 1; return GetLastK(data, length, k, start, end); } |
在分别找到第一个k和最后一个k的下标之后，就能计算出k在数组中出现的次数了。相应的代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int GetNumberOfK( int *data, int length, int k) { int number = 0; if (data != NULL && length > 0) { int first = GetFirstK(data, length, k, 0, length - 1); int last = GetLastK(data, length, k, 0, length - 1); if (first > -1 && last > -1) number = last - first + 1; } return number; } |
完整代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | int GetFirstK( int *data, int length, int k, int start, int end) { if (start > end) return -1; int middleIndex = start + ((end - start) >> 1); int middleData = data[middleIndex]; if (middleData == k) { if ((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0) return middleIndex; else end = middleIndex - 1; } else if (middleData > k) end = middleIndex - 1; else start = middleIndex + 1; return GetFirstK(data, length, k, start, end); } int GetLastK( int *data, int length, int k, int start, int end) { if (start > end) return -1; int middleIndex = start + ((end - start) >> 1); int middleData = data[middleIndex]; if (middleData == k) { if ((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length -1) return middleIndex; else start = middleIndex + 1; } else if (middleData < k) start = middleIndex + 1; else end = middleIndex - 1; return GetLastK(data, length, k, start, end); } int GetNumberOfK( int *data, int length, int k) { int number = 0; if (data != NULL && length > 0) { int first = GetFirstK(data, length, k, 0, length - 1); int last = GetLastK(data, length, k, 0, length - 1); if (first > -1 && last > -1) number = last - first + 1; } return number; } |
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3642322.html，如需转载请自行联系原作者