怎樣在排序數(shù)組中查找數(shù)字

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

題目:
統(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，如果是，說明這個(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ù)組是有序的，我們可以考慮利用二分查找的方法來解決這個(gè)問題。
    如果我們先利用二分查找定位到了這個(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，如果不是，說明這個(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ù)字了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。