這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)怎樣在排序數(shù)組中查找數(shù)字，文章內(nèi)容豐富且以專(zhuān)業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

禪城網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)從2013年開(kāi)始到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

題目:
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù). 例如輸入排序數(shù)組{1,2,3,3,3,3,4,5},由于3在這個(gè)數(shù)中出現(xiàn)了4次,輸出4.

# -*- coding: utf-8 -*-
# @Time         : 2019-07-13 15:10
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getNumberOfK.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

def getFirstK(data, k):
    start, end = 0, len(data) - 1
    while start <= end:
        mid = (start + end) >> 1
        if data[mid] == k:
            # 關(guān)鍵在于，如果mid是k，那么就判斷前一個(gè)元素是不是也是k，如果是，說(shuō)明這個(gè)位置不是
            # 第一次出現(xiàn)，要在左邊繼續(xù)查找。否則，直接返回mid，因?yàn)槭堑谝淮纬霈F(xiàn)了
            if mid - 1 >= start and data[mid - 1] == k:
                end = mid - 1
            else:
                return mid
        elif data[mid] < k:
            start = mid + 1
        else:
            end = mid - 1

    return -1

def getLastK(data, k):
    start, end = 0, len(data) - 1
    while start <= end:
        mid = (start + end) >> 1
        if data[mid] == k:
            if mid + 1 <= end and data[mid + 1] == k:
                start = mid + 1
            else:
                return mid
        elif data[mid] < k:
            start = mid + 1
        else:
            end = mid - 1

    return -1

def getNumberOfK(data, k):
    """
    要獲取一個(gè)有序數(shù)組中某個(gè)元素出現(xiàn)的次數(shù)，最直觀的做法就是遍歷整個(gè)數(shù)組，然后統(tǒng)計(jì)該元素的出現(xiàn)次數(shù)，
    這樣做的時(shí)間復(fù)雜度是O(n)

    但是由于這個(gè)數(shù)組是有序的，我們可以考慮利用二分查找的方法來(lái)解決這個(gè)問(wèn)題。
    如果我們先利用二分查找定位到了這個(gè)元素，然后再往前往后遍歷，這樣的話時(shí)間復(fù)雜度也還是O(n)。

    但是如果我們?cè)诶枚植檎业臅r(shí)候，想辦法定位這個(gè)元素第一次出現(xiàn)的下標(biāo)和最后一次出現(xiàn)的下標(biāo)。
    在利用二分查找找到一個(gè)這個(gè)元素之后，判斷這個(gè)元素是否是第一個(gè)，也就是對(duì)比這個(gè)元素的前一個(gè)是否也
    是k，如果不是，說(shuō)明這個(gè)元素就是第一個(gè)元素，否則在這個(gè)下標(biāo)的左邊繼續(xù)查找。
    對(duì)于最后一次出現(xiàn)的下標(biāo)同理。
    """
    if not data:
        return 0
    first = getFirstK(data, k)
    last = getLastK(data, k)
    if first != -1 and last != -1:
        return last - first + 1
    else:
        return 0

def main():
    data = [1, 2, 3, 3, 3, 3, 4, 5]
    k = 3
    print(getNumberOfK(data, k))

if __name__ == '__main__':
    main()

上述就是小編為大家分享的怎樣在排序數(shù)組中查找數(shù)字了，如果剛好有類(lèi)似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前名稱(chēng)：怎樣在排序數(shù)組中查找數(shù)字-創(chuàng)新互聯(lián)
本文URL：http://weahome.cn/article/decpoh.html