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

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

题目描述

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

利用map建立映射关系, 做题以来思路最快, 变的最快, 提交一次过

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        map<int, int> myMap;
        
        for (int i = 0; i < data.size(); i++) {
            myMap[data[i]]++;
        }
        
        return myMap[k];
    }
};

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.empty()) return 0;
        
        int count = 0;
        int low = 0;
        int high = data.size() - 1;
        
        while (true) {
            int mid = (low + high) / 2;
            if (data[mid] == k) {
                int temp = mid;
                while ((temp <= high) && (data[temp] == k)) {
                    count++;
                    temp++;
                }
                temp = mid;
                while ((temp >= 0) && (data[temp] == k)) {
                    count++;
                    temp--;
                }
                return count-1;
            }
            else if (low > high) {
                return 0;
            }
            else {
                if (data[mid] > k) {
                    high = mid - 1;
                }
                else {
                    low = mid + 1;
                }
            }
        }
    }
};