剑指offer 面试题38

面试题38：数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1，2，3，3，3，3，4，5}和数字3，由于3在这个数组中出现了4次，因此输出4。

主要的思路是进行二分搜索找到第一个位置和最后一个位置，一开始的代码如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 
 4 int num[102];
 5 int n;
 6 
 7 int getFirstk(int from, int to, int k) {
 8     if(to < from) {
 9         return -1;
10     }
11 
12     int mid = (from+to)/2;
13     if(num[mid] < k) {
14         return getFirstk(mid+1,to,k);
15     }
16     else if(num[mid] > k) {
17         return getFirstk(from,mid-1,k);
18     }
19     else {
20         if(mid == 0) {
21             return 0;
22         }
23         if(num[mid-1] == k) {
24             return getFirstk(from,mid-1,k);
25         }
26         else if(num[mid-1] != k) {
27             return mid;
28         }
29     }
30 }
31 
32 int getLastK(int from, int to, int k) {
33     if(to < from) {
34         return -1;
35     }
36 
37     int mid = (from+to)/2;
38     if(num[mid] < k) {
39         return getLastK(mid+1,to,k);
40     }
41     else if(num[mid] > k) {
42         return getLastK(from, mid-1, k);
43     }
44     else {
45         if(mid == n-1) {
46             return mid;
47         }
48         else {
49             if(num[mid+1] == k) {
50                 return getLastK(mid+1,to,k);
51             }
52             else {
53                 return mid;
54             }
55         }
56     }
57 }
58 
59 int main(int argc, char const *argv[])
60 {
61     
62     while(scanf("%d",&n) != EOF) {
63         for(int i = 0; i < n; i++) {
64             scanf("%d",&num[i]);
65         }
66         int k;
67         scanf("%d",&k);
68         int from = getFirstk(0,n-1,k);
69         int to = getLastK(0,n-1,k);
70         int ans;
71         
72             ans = to - from+1;
73         
74         printf("%d
",ans);
75     }    
76     return 0;
77 }

这段代码的主要问题在于没有考虑元素没有找到的情况，倘若都没找到，from和to都为-1，则会导致结果为1

修改如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 
 4 int num[102];
 5 int n;
 6 
 7 int getFirstk(int from, int to, int k) {
 8     if(to < from) {
 9         return -1;
10     }
11 
12     int mid = (from+to)/2;
13     if(num[mid] < k) {
14         return getFirstk(mid+1,to,k);
15     }
16     else if(num[mid] > k) {
17         return getFirstk(from,mid-1,k);
18     }
19     else {
20         if(mid == 0) {
21             return 0;
22         }
23         if(num[mid-1] == k) {
24             return getFirstk(from,mid-1,k);
25         }
26         else if(num[mid-1] != k) {
27             return mid;
28         }
29     }
30 }
31 
32 int getLastK(int from, int to, int k) {
33     if(to < from) {
34         return -1;
35     }
36 
37     int mid = (from+to)/2;
38     if(num[mid] < k) {
39         return getLastK(mid+1,to,k);
40     }
41     else if(num[mid] > k) {
42         return getLastK(from, mid-1, k);
43     }
44     else {
45         if(mid == n-1) {
46             return mid;
47         }
48         else {
49             if(num[mid+1] == k) {
50                 return getLastK(mid+1,to,k);
51             }
52             else {
53                 return mid;
54             }
55         }
56     }
57 }
58 
59 int main(int argc, char const *argv[])
60 {
61     
62     while(scanf("%d",&n) != EOF) {
63         for(int i = 0; i < n; i++) {
64             scanf("%d",&num[i]);
65         }
66         int k;
67         scanf("%d",&k);
68         int from = getFirstk(0,n-1,k);
69         int to = getLastK(0,n-1,k);
70         int ans;
71         if(from == -1 || to == -1) {
72             ans = 0;
73         }
74         else {
75             ans = to - from+1;
76         }
77         printf("%d
",ans);
78     }    
79     return 0;
80 }

找到一个在线测试的oj

http://www.nowcoder.com/books/coding-interviews/70610bf967994b22bb1c26f9ae901fa2?rp=2

此oj的编译条件很严格，而且形式与平常的oj略有不同，花了一点时间来适应，ac代码如下

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         int n = data.size();
 5         if(n < 0) {
 6             return 0;
 7         }
 8         int from = getFirstk(data,0,n-1,k);
 9         int to = getLastK(data,0,n-1,k,n);
10         if(from == -1 || to == -1) {
11             return 0;
12         }
13         int ans = to - from+1;
14         return ans;
15     }
16     
17     int getFirstk(const vector<int> &num,int from, int to, int k) {
18         if(to < from) {
19             return -1;
20         }
21 
22         int mid = (from+to)/2;
23         if(num[mid] < k) {
24             return getFirstk(num,mid+1,to,k);
25         }
26         else if(num[mid] > k) {
27             return getFirstk(num,from,mid-1,k);
28         }
29         else {
30             if(mid == 0) {
31                 return 0;
32             }
33             if(num[mid-1] == k) {
34                 return getFirstk(num,from,mid-1,k);
35             }
36             else if(num[mid-1] != k) {
37                 return mid;
38             }
39         }
40         return -1;
41     }
42 
43     int getLastK(const vector<int> &num,int from, int to, int k, int n) {
44         if(to < from) {
45             return -1;
46         }
47 
48         int mid = (from+to)/2;
49         if(num[mid] < k) {
50             return getLastK(num,mid+1,to,k,n);
51         }
52         else if(num[mid] > k) {
53             return getLastK(num,from, mid-1, k,n);
54         }
55         else {
56             if(mid == n-1) {
57                 return mid;
58             }
59             else {
60                 if(num[mid+1] == k) {
61                     return getLastK(num,mid+1,to,k,n);
62                 }
63                 else {
64                     return mid;
65                 }
66             }
67         }
68         return -1;
69     }
70 };