劍指Offer（37）：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

一、引子

這個系列是我在?？途W(wǎng)上刷《劍指Offer》的刷題筆記，旨在提升下自己的算法能力。

二、題目

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

1、思路

看見有序，肯定就是二分查找了

做法就是使用二分法找到數(shù)字在數(shù)組中出現(xiàn)的第一個位置，再利用二分法找到數(shù)字在數(shù)組中出現(xiàn)的最后一個位置。時間復(fù)雜度為O(logn + logn)，最終的時間復(fù)雜度為O(logn)。

舉個例子，找到數(shù)字k在數(shù)組data中出現(xiàn)的次數(shù)。

數(shù)組data中，數(shù)字k出現(xiàn)的第一個位置：

我們對數(shù)組data進行二分，如果數(shù)組中間的數(shù)字小于k，說明k應(yīng)該出現(xiàn)在中間位置的右邊；如果數(shù)組中間的數(shù)字大于k，說明k應(yīng)該出現(xiàn)在中間位置的左邊；如果數(shù)組中間的數(shù)字等于k，并且中間位置的前一個數(shù)字不等于k，說明這個中間數(shù)字就是數(shù)字k出現(xiàn)的第一個位置。

同理，數(shù)字k出現(xiàn)的最后一個位置，也是這樣找的。但是判斷少有不同。我們使用兩個函數(shù)分別獲得他們。

2、編程實現(xiàn)

python

代碼實現(xiàn)方案：
python有自帶的方法進行查找~

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)

分享技術(shù)，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關(guān)注！

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

審核編輯 黃昊宇