数字在排序数组中出现的次数

剑指offer 二分查找

Created At : 2019-12-26 23:12

Count:413 Views 👀 :

Comment:

题目描述
1. 思路

题目描述

统计一个数字在排序数组中出现的次数。

思路

二分查找，找出目标数字第一次出现的位置，和最后一次出现的位置

class Solution {
private:
    // 找到数组中第一个k的下标。如果数组中不存在k，返回-1
    int GetFirstK(vector<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的下标。如果数组中不存在k，返回-1
    int GetLastK(vector<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);
    }
public:
    // 被调用的方法
    int GetNumberOfK(vector<int> data ,int k) {
        int number = 0;
        
        if(data.size() > 0)
        {
            // 找第一次出现的位置
            int first = GetFirstK(data, data.size(), k, 0, data.size() - 1);
            // 找最后一次出现的位置
            int last = GetLastK(data, data.size(), k, 0, data.size() - 1);

            if(first > -1 && last > -1) {
                number = last - first + 1;
            }
        }

        return number;
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com