This article is going to talk about an algorithm problem, not difficult, can be said to be small white level, is about an array to calculate the number of repetitions of an element of the problem.

Look at the following unordered array and find the number of occurrences of the number 2. How about super simple 🙂

,2,1,1,2,3,5,2,3,3,4,5,7,6,2 [0]Copy the code

So the way you can think of it, you go through the for loop, you hit 2 and you start counting and you add one, and the number of 2 is just counting.

Very good. That would certainly solve the problem.

Here is an implementation of the above idea, using c++ code. It is important to note that templates in c++, commonly known as generics, should be used. Because we don’t know exactly what type a given array element is, except that the array element given above is an integer, it could be a string, or a custom object.

template <typename T>
int countOccurrences(vector<T> arr, T target){
    
    int result = 0;
    for (int i = 0; i < arr.size(); i++) {
        if(target == arr[i]) { result++; }}return result;
}

Copy the code

Is there any other way? That’s when you can think about, oh, we can also solve this problem by using lookup tables, where the element values are the keys, and the values are the number of identical elements in the array. It takes a for loop to count the same elements, and then returns the value of the corresponding element in the lookup table.

Give the code:

template <typename T>
int countOccurrences(vector<T> arr, T target){
    
    unordered_map<T, int> map;
    for (int i = 0; i < arr.size(); i++) {
        map[arr[i]]++;
    }
    
    return map[target];
}
Copy the code

Think about it. What if this array became ordered? Can you think of another way to solve this problem?

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]Copy the code

At this point you can use binary search, binary search is mainly to solve the search problem of ordered sets. But the problem is, there are four 2’s, binary search can only find one of the 2’s, this…. I don’t think binary search works either.

If you have this question, you can first follow the idea of binary search, stop to think about how to use binary search to solve the problem.

To continue.

In fact, we can use a second binary search, where the first search is for the left edge of the search value, and the second search is for the right edge of the search value.

Give the code first, and then walk through the code.

template <typename T>
int countOccurrences(vector<T> arr, T target){
    
    int low_left = 0;
    int high_left = arr.size();
    
    while (low_left < high_left) {
        int middle = low_left + (high_left - low_left) / 2;
        if (arr[middle] < target) {
            low_left = middle + 1;
        } else {
            high_left = middle;
        }
    }
    
    int low_right = 0;
    int high_right = arr.size();
    
    while (low_right < high_right) {
        int middle = low_right + (high_right - low_right) / 2;
        if (arr[middle] > target) {
            high_right = middle;
        } else{ low_right = middle + 1; }}return low_right - low_left;
}
Copy the code

I’m going to follow the logic of how the program works step by step.

First of all, this is the array that we passed in, looking for the repeating element of 2

The vector < int > vec = vector < int >,1,1,2,2,2,2,3,3,3,4,5,5,6,7 {0}. int result = countOccurrences(vec, 2);Copy the code

Before the first while loop, set two variables, low_left and high_left. My definition of these two values is to find the target value in the interval [low_left,high_left]. Note that the interval is front-closed and back-open, so the initial values for these two values are set to low_left = 0 and high_left = arr.size().

After the first loop, middle = 7, arr[7] = 3, 3 is greater than 2, so high_left = 7, as shown in the array below, high_left points to 3. For viewing purposes, # indicates the low_left location and * indicates the high_left location.

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *
Copy the code

In the second loop, middle = 3,arr[3] = 2, high_left = 3, high_left = 3, middle = 3,arr[3] = 2, high_left = 3, high_left = 3 I’m going to keep looking to the left. Because we’re looking for where the 2 first appears.

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *
Copy the code

Continue the third loop, middle = 1,arr[1] = 1,1 is less than 2, so low_left = middle + 1 should be equal to 2.

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *
Copy the code

Continue the fourth loop, middle = 2 + (3-2) / 2 = 2, arr[2] = 1, 1 is less than 2, so at this point low_left continues to increment, low_left = 3, end the loop. At this point, we’ve found where 2 first appears, as shown here.

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]#
       *
Copy the code

The logic of finding the right edge is similar to the logic of finding the left edge, so I’m not going to give you a picture of it, but instead of finding the left edge, once you find the 2, you keep looking to the right where the 2 ends.

,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]# *,1,1,2,2,2,2,3,3,3,4,5,5,6,7 [0]#
               *
Copy the code

So the right margin is where the index is at 7, so the number of occurrences of 2 is the right margin minus the left margin, which is 7 minus 3 is 4.

Let’s talk about a special case.

The current array does not contain elements to look up. So low_right and low_left will return the same number, subtracting the two numbers equals zero,

To summarize, in this method, after finding a value, the search does not stop, but continues to the left or right to find the starting and ending positions of the target value. It can be seen that on the basis of mastering basic knowledge, it is very important to be able to use it flexibly.