CodingInterviews/38_NumberOfK.cpp at master · wjmj/CodingInterviews · GitHub

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
#include <iostream>

using namespace std;

int getNumberOfK(int* nums, int length, int k)
{
    if ((nums == NULL) || (length <= 0))
        return 0;

    int left = 0;
    int right = length - 1;
    int mid = 0;
    while (left <= right)
    {
        mid = (left+right)/2;
        if (nums[mid] == k)
            break;
        else if (nums[mid] > k)
            right = mid-1;
        else
            left = mid+1;
    }

    if (left > right)
        return 0;
    int i = mid;
    while ((i >= 0) && (nums[i] == nums[mid]))
        i--;
    int j = mid;
    while ((j < length) && (nums[j] == nums[mid]))
        j++;

    return j-i-1;
}


//======================Test Code==================
static void test(const char* testName, int* nums, int length, int k, int expected)
{
    cout << testName << " Begins: ";
    int count = getNumberOfK(nums, length, k);
    if (count == expected)
        cout << "Passed." << endl;
    else
        cout << "Failed." << endl;
}

static void test1()
{
    int nums[] = {1, 2, 3, 3, 3, 3, 4, 5};
    int length = 8;
    int k = 3;
    test("test1", nums, length, k, 4);
}

static void test2()
{
    int* nums = NULL;
    int length = 0;
    int k = 1;
    test("test2", nums, length, k, 0);
}

int main()
{
    test1();
    test2();

    return 0;
}