劍指offer：最小的k個(gè)數(shù)

題目描述
輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,。

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括隆德網(wǎng)站建設(shè)、隆德網(wǎng)站制作、隆德網(wǎng)頁(yè)制作以及隆德網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，隆德網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到隆德省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

# -*- coding: utf-8 -*-
# @Time         : 2019-07-08 21:09
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getLeastNumbers.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    從數(shù)組中尋找最小的k個(gè)數(shù)字，一般來(lái)說(shuō)最直接的做法就是先將這個(gè)數(shù)組排序，然后取最小的k個(gè)數(shù)字即可。
    但是這樣做的時(shí)間復(fù)雜度為O(nlogn)

    解法1：
    借鑒快排中partition()的做法，因?yàn)閜artition()每次可以確定一個(gè)下標(biāo)的正確元素，并保證其左右與其
    大小關(guān)系有序。所以只要我們通過(guò)partition()確定了下標(biāo)為k-1的元素，那么其左邊都是小于該元素的。
    時(shí)間復(fù)雜度為O(n)

    解法2：
    可以維護(hù)一個(gè)容量為k的容器，然后遍歷整個(gè)數(shù)組，如果遇到比容器中最大值要小的元素，那么就將這個(gè)元素
    替換容器中的最大值。時(shí)間復(fù)雜度為O(nlogk)
    """
    def GetLeastNumbers_Solution1(self, tinput, k):
        if k <= 0 or k > len(tinput):
            return []

        ans = tinput[:k]
        for i in range(k, len(tinput)):
            if tinput[i] < max(ans):
                ans.remove(max(ans))
                ans.append(tinput[i])

        return sorted(ans)

    def GetLeastNumbers_Solution2(self, tinput, k):
        def partition(begin, end):
            pos = begin
            for i in range(begin, end):
                if tinput[i] < tinput[end]:
                    tinput[i], tinput[pos] = tinput[pos], tinput[i]
                    pos += 1
            tinput[end], tinput[pos] = tinput[pos], tinput[end]
            return pos

        if k <= 0 or k > len(tinput):
            return []

        start, stop = 0, len(tinput) - 1
        idx = partition(start, stop)
        while idx != k - 1:
            if idx > k:
                stop = idx - 1
            else:
                start = idx + 1
            idx = partition(start, stop)

        return sorted(tinput[: k])

def main():
    nums = [4, 5, 1, 6, 2, 7, 3, 8]
    k = 4
    solution = Solution()
    print(solution.GetLeastNumbers_Solution2(nums, k))

if __name__ == '__main__':
    main()

本文名稱：劍指offer：最小的k個(gè)數(shù)
網(wǎng)頁(yè)鏈接：http://bm7419.com/article36/ipoisg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供、網(wǎng)站營(yíng)銷、品牌網(wǎng)站設(shè)計(jì)、用戶體驗(yàn)、網(wǎng)站設(shè)計(jì)、Google

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容