-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgetcount.cpp
More file actions
104 lines (94 loc) · 2.57 KB
/
Copy pathgetcount.cpp
File metadata and controls
104 lines (94 loc) · 2.57 KB
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<stdio.h>
#include <assert.h>
#include<stdlib.h>
#include <algorithm>
#include<vector>
using namespace std;
int getcount(vector<int>& nums, int target)
{
int size = nums.size();
if (nums[0] > target) return 0;
if (nums[size-1] < target) return 0;
int first = -1;
int last = -1;
if (nums[0] == target) {
first = 0;
}
if (nums[size-1] == target) {
last = size-1;
}
//find first
if (first == -1) {
int start = 0;
int end = size-1;
while (start < end-1) {
int half = (start + end)/2 ;
// printf("start=%d, half=%d, end=%d, val=%d\n", start, half, end, nums[half]);
if (nums[half] < target) {
start = half;
} else {
end = half;
}
}
if (nums[start+1] == target) {
first = start+1;
}
}
if (first == -1) {
return 0;
}
// printf("find first=%d\n", first);
//find last
if (last == -1) {
int start = first;
int end = size-1;
while (start < end-1) {
int half = (start + end)/2 ;
// printf("start=%d, half=%d, end=%d, val=%d\n", start, half, end, nums[half]);
if (nums[half] > target) {
end = half;
} else {
start = half;
}
}
last = end -1;
}
// printf("fist=%d, first-v=%d, firstv=%d, last=%d, lastv=%d last+1v=%d\n",
// first, first == 0 ? -1 : nums[first-1], nums[first], last, nums[last], last == size-1 ? 0xfffffff : nums[last+1]);
return last - first + 1;
}
#define MAX 100
int getr()
{
return rand() % MAX + 30;
}
int main(int argc, char** argv)
{
vector<int> nums;
if (argc > 1) {
srand(atoi(argv[1]));
}
int totalcount = 0;
int total = getr();
int targetcount = 0;
int targetval = -1;
while (total-- > 0) {
int count = getr();
int val = getr();
nums.insert(nums.end(), count, val);
totalcount += count;
if (targetval == -1 || targetval == val) {
targetcount += count;
targetval = val;
}
}
sort(nums.begin(), nums.end());
// printf("init done, totalcount=%d, targetval=%d, targetc=%d\n", totalcount, targetval, targetcount);
for (int i = 0; i < nums.size(); i++) {
// printf("yunfei, %d\n", nums[i]);
}
int ret = getcount(nums, targetval);
// printf("targetv=%d, targetc=%d, ret=%d\n", targetval, targetcount, ret);
assert(targetcount == ret);
return 0;
}