本文共 3605 字，大约阅读时间需要 12 分钟。

���������������������������������������������������

���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

������

���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������������������������

������������������������������������������������������������������������������������������������������������������������������������������

���������C++������������������������

int GetNumberOfK(std::vector
   
     data, int k) {
    if (data.size() < 1) {
        return 0;
    }
    int left = leftLimit(data, k, 0, data.size());
    int right = rightLimit(data, k, -1, data.size() - 1);
    return (right - left + 1);
}
int rightLimit(std::vector
    
      data, int k, int left, int right) {
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (data[mid] <= k) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return right;
}
int leftLimit(std::vector
     
       data, int k, int left, int right) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (data[mid] >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
     
    
   

������������

• leftLimit������������������������������������������k������������
• rightLimit���������������������������������������������k������������
• ������������������������������right - left + 1���

������������������STL���������������

C++���������������������std::equal_range������������������������������������������������������������������������������������������������������

int GetNumberOfK(std::vector
   
     data, int k) {
    auto resultPair = std::equal_range(data.begin(), data.end(), k);
    return resultPair.second - resultPair.first;
}
   

������������

• std::equal_range������pair���������������pair.first������������������k������������pair.second���������������������k������������
• ������������������������������������������������

������������������������������������������

���������������������������������������������k-0.5���k+0.5������������������������������������������

int GetNumberOfK(std::vector
   
     data, int k) {
    int start = biSearch(data, k - 0.5);
    int end = biSearch(data, k + 0.5);
    return end - start;
}
int biSearch(const std::vector
    
     & data, double num) {
    int s = 0, e = data.size() - 1;
    while (s <= e) {
        int mid = (e - s) / 2 + s;
        if (data[mid] < num) {
            s = mid + 1;
        } else if (data[mid] > num) {
            e = mid - 1;
        }
    }
    return s;
}
    
   

������������

• biSearch���������������������������������������������������������k-0.5���k+0.5������������������������
• start������������������k������������end���������������������k������������
• ���������������end - start���

���������������