劍指Offer（三十七）：數字在排序陣列中出現的次數
搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
github：https://github.com/aimi-cn/AILearners
一、引子
這個系列是我在牛客網上刷《劍指Offer》的刷題筆記，旨在提升下自己的演算法能力，
查看完整的劍指Offer演算法題決議請點擊CSDN和github鏈接：
劍指Offer完整習題決議CSDN地址
github地址
二、題目
統計一個數字在排序陣列中出現的次數，
1、思路
看見有序，肯定就是二分查找了
做法就是使用二分法找到數字在陣列中出現的第一個位置，再利用二分法找到數字在陣列中出現的最后一個位置，時間復雜度為O(logn + logn)，最終的時間復雜度為O(logn)，
舉個例子，找到數字k在陣列data中出現的次數，
陣列data中，數字k出現的第一個位置：
我們對陣列data進行二分，如果陣列中間的數字小于k，說明k應該出現在中間位置的右邊；如果陣列中間的數字大于k，說明k應該出現在中間位置的左邊；如果陣列中間的數字等于k，并且中間位置的前一個數字不等于k，說明這個中間數字就是數字k出現的第一個位置，
同理，數字k出現的最后一個位置，也是這樣找的，但是判斷少有不同，我們使用兩個函式分別獲得他們，
2、編程實作
python
代碼實作方案：
python有自帶的方法進行查找~
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
return data.count(k)
AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料
分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/72035.html
標籤：其他
下一篇：論文翻譯：ASRWGAN: Wasserstein Generative Adversarial Network for Audio Super Resolution