《劍指offer》刷題筆記（時間效率）：最小的K個數

• 轉載請注明作者和出處：http://blog.csdn.net/u011475210
• 代碼位址：https://github.com/WordZzzz/Note/tree/master/AtOffer
• 刷題平台：https://www.nowcoder.com/
• 題  庫：劍指offer
• 編  者：WordZzzz

• 劍指offer刷題筆記時間效率最小的K個數
  • 題目描述
  • 解題思路
  • C版代碼實作
    • 思路一
    • 最大堆
    • 紅黑樹
  • Python版代碼實作
    • 思路一

題目描述

輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。

解題思路

思路一：結合快排。排序後直接for循環将最小的K個數填入結果。時間複雜度O（NlogK）。

思路二：最大堆或者紅黑樹。我們可以先建立一個大小為K的資料容器來存儲最小的k個數字，然後每次從N個整數中讀取一個數。如果容器中已有的數字個數少于K，則直接把這次讀入的整數放入容器中；如果容器中已經有K個數了，此時我們需要找出容器中的最大值，然後與待插入的整數進行比較，誰小就留着誰。

我們再來捋一遍，容器滿了之後我們要做的三件事情：一是在k個證書中找到最大數；二是有可能在這個容器中删除最大數；三是有可能要插入一個新的數字。如果用一個二叉樹來實作這個資料容器，那麼我們能在O(logK)時間内實作這三步操作。是以對于N個輸入數字而言，總時間效率就是O(Nlogk)。

最大堆：根結點的值總是大于它的子樹中任意結點的值。我們需要O(1)時間得到最大值，O(logK)時間來完成删除及插入操作；

紅黑樹：根據一定規則確定樹在一定程度上是平衡的，進而保證在紅黑樹種查找、删除和插入操作都隻需要O(logK)時間。

Python中沒有現成的最大堆或者紅黑樹實作，本渣渣就不再這裡折騰了。

C++版代碼實作

思路一

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.empty() || k > input.size())
            return res;

        sort(input.begin(), input.end());

        for(int i = ; i < k; ++i)
            res.push_back(input[i]);

        return res;
    }
};
           

最大堆

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len = input.size();
        if(len <=  || k > len || k <= )
            return vector<int>();
        vector<int> res(input.begin(), input.begin()+k);
        //建堆
        make_heap(res.begin(), res.end());

        for(int i=k; i < len; i++)
        {
            if(input[i] < res[])
            {
                //先pop,然後在容器中删除
                pop_heap(res.begin(), res.end());
                res.pop_back();
                //先在容器中加入，再push
                res.push_back(input[i]);
                push_heap(res.begin(), res.end());
            }
        }
        //使其從小到大輸出
        sort_heap(res.begin(), res.end());
        return res;
    }
};
           

紅黑樹

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len = input.size();
        if(len <=  || k > len || k <= )
            return vector<int>();
        //仿函數中的greater<T>模闆，從大到小排序
        multiset<int, greater<int> > leastNums;
        vector<int>::iterator vec_it = input.begin();
        for(; vec_it != input.end(); vec_it++)
        {
            //将前k個元素插入集合
            if(leastNums.size() < k)
                leastNums.insert(*vec_it);
            else
            {
                //第一個元素是最大值
                multiset<int, greater<int> >::iterator greatest_it = leastNums.begin();
                //如果後續元素<第一個元素，删除第一個，加入目前元素
                if(*vec_it < *(leastNums.begin()))
                {
                    leastNums.erase(greatest_it);
                    leastNums.insert(*vec_it);
                }
            }
        }
        return vector<int>(leastNums.begin(), leastNums.end());
    }
};
           

Python版代碼實作

思路一

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if tinput is None:
            return
        n = len(tinput)
        if n < k:
            return []
        tinput = sorted(tinput)
        return tinput[:k]
           

系列教程持續釋出中，歡迎訂閱、關注、收藏、評論、點贊哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz