算法-数字在排序数组中出现的次数

灰太狼 2022-06-10 03:29 155阅读 0赞

**题目：**  
统计一个数字在排序数组中出现的次数，比如排序数组为\{1,2,3,3,3,4,5\}，那么数字3出现的次数就是3。

**解题思路：**  
1.首先，遍历数组肯定就能知道某个数字的个数，此时的时间复杂度O(n)。  
2.除此之外，我们注意到，任务本质上是**查找**问题，而且是**排序好**的**数组**，可以尝试用二分查找算法，这样我们可以找到一个3，然后根据这个3向数组的两端遍历，找到所有的3，但是如果3是n个呢？这个算法本质上时间复杂度还是O(n)。  
3.最后，我们发现在排序数组中，如果我们知道了第一个3和最后一个3出现的位置，那么其实也就知道了个数，那么我们能否在第一次使用二分查找之后，继续使用二分法，找到两端的3？  
显然可以的，只不过不要稍微修改一些传统二分查找的规则：  
如果中间的数字大于3，那么第一个和最后一个3肯定在左半边；  
![这里写图片描述][c1a801646ae28533b412929d28000bf8.png]  
如果中间的数字小于3，那么第一个和最后一个3肯定在右半边；  
![这里写图片描述][c20d94d84b3b036ba35a6b9a885d2d5c.png]  
如果中间的数字等于3，那么需要判断这个3是不是第一个或最后一个3：  
如果中间数字左侧相邻的数是3，那么第一个3一定在左半边：  
![这里写图片描述][618f6bb3dba34ee7855a18b4eb6bab23.png]  
如果中间数字左侧相邻的数不是3，那么第一个3就在中间：  
![这里写图片描述][1ed49d68d2578b513a1d3a4545db6776.png]  
如果中间数字右侧相邻的数是3，那么最后一个3一定在右半边：  
![这里写图片描述][51b875c75cb51231e533e957b957e3aa.png]  
如果中间数字右侧相邻的数不是3，那么最后一个3一定就在中间：  
![这里写图片描述][3aad58e4886a4c96ebddb6aefe19dc91.png]  
所以，我们可以把找第一个和最后一个分成两个问题来考虑，用两个函数分别返回在数组中的位置，那么他们的差值+1就是个数。

个人感觉，二分查找的关键在于用一种规则，让每次查找之后的范围都可以减半，以此来降低时间复杂度，所以改进的二分查找可以很多问题中灵活使用，除了这个，在[旋转数组的最小数字][Link 1]问题中也可以用到，甚至在旋转数组的最小数字中，连二分查找的前提条件都变了，不再是一个顺序的数组。

**代码实现**

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;
    }
    //找第一个k
    int GetFirstK(int* data, int length, int k, int start, int end)
    {
        if(start > end)
            return -1;
    
        int middleIndex = (start + end) / 2;
        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
    int GetLastK(int* data, int length, int k, int start, int end)
    {
        if(start > end)
            return -1;
    
        int middleIndex = (start + end) / 2;
        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);
    }

`GetNumberOfK`函数没啥好说的，就是在调用，剩下的`GetFirstK`和`GetLastK`逻辑是一样的，只要理解一个就好了。  
在`GetFirstK`中，使用了递归的方法，在下一次递归前，一直在调整数组范围，让下一次递归与本次递归相比，范围少了一半，这就是二分。  
递归退出的条件就是：

if((middleIndex > 0 && data[middleIndex - 1] != k) 
                || middleIndex == 0)

[c1a801646ae28533b412929d28000bf8.png]: /images/20220610/3cf6b5f3d2534c9e82ca50e4e89955ce.png
[c20d94d84b3b036ba35a6b9a885d2d5c.png]: /images/20220610/e3b845b5a281471db0c9ea711c29f171.png
[618f6bb3dba34ee7855a18b4eb6bab23.png]: /images/20220610/71e8687c0d3949d2ba4dda6a04f299df.png
[1ed49d68d2578b513a1d3a4545db6776.png]: /images/20220610/c7dfa7ec0cc3450a8be90a0d5d6eb7bc.png
[51b875c75cb51231e533e957b957e3aa.png]: /images/20220610/ca46ed6969d249bf9455ccf0c0003cfe.png
[3aad58e4886a4c96ebddb6aefe19dc91.png]: /images/20220610/39e458979722424c926ec37076db5e9c.png
[Link 1]: http://blog.csdn.net/chaipp0607/article/details/76855379