Given n numbers, find out the least k numbers from them I have been solving the following problem:


  Given n numbers find out the least k numbers from them. For example, if there are 8 numbers like 5,6,3,4,7,8,9,-1. For k = 3 the result will be -1,3,4.


I implemented it in the following way:


make heap with first k numbers
traverse the rest k-n numbers

if heapMax > any of the k numbers then
swap

return heap containing k numbers


Can you please review my code and provide me with feedback?

#include &lt;iostream&gt;
#include &lt;set&gt;
#include &lt;vector&gt;

std::vector&lt;int&gt; getKLeastNumbers(std::vector&lt;int&gt; &amp;nums, int k)
{
    std::vector&lt;int&gt; tmpNums;

    if(k&lt;=0 || k &gt; nums.size())
    {
        return tmpNums;
    }

    for(int i=0; i&lt;k; i++)
    {
        tmpNums.push_back(nums.at(i));
    }
    std::make_heap(tmpNums.begin(), tmpNums.end());

    for(int i=k; i&lt;nums.size(); i++)
    {
        if (tmpNums.front() &gt; nums.at(i))
        {
            int tmp = nums.at(i);

            nums.at(i) = tmpNums.front();

            std::pop_heap(tmpNums.begin(),tmpNums.end());
            tmpNums.pop_back();

            tmpNums.push_back(tmp);
            std::push_heap(tmpNums.begin(), tmpNums.end());
        }
    }

    return tmpNums;
}

int main()
{
    // test codes
    std::vector&lt;int&gt;nums;
    nums.push_back(56);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(60);
    nums.push_back(-6);
    nums.push_back(3);
    nums.push_back(600);

    nums = getKLeastNumbers(nums,1);

    for(int i=0; i&lt;nums.size(); i++)
    {
        std::cout&lt;&lt;nums.at(i)&lt;&lt;std::endl;
    }

    std::vector&lt;int&gt;nums2;
    nums2.push_back(56);

    nums2 = getKLeastNumbers(nums2,-1);

    std::cout&lt;&lt;std::endl&lt;&lt;"Test set 2 "&lt;&lt;std::endl;
    for(int i=0; i&lt;nums2.size(); i++)
    {
        std::cout&lt;&lt;nums2.at(i)&lt;&lt;std::endl;
    }
}
I assume you can use C++11.


Use initializer lists:

std::vector&lt;int&gt;nums;
nums.push_back(56);
nums.push_back(5);
nums.push_back(6);
nums.push_back(60);
nums.push_back(-6);
nums.push_back(3);
nums.push_back(600);


becomes

std::vector&lt;int&gt; nums = {56, 5, 6, 60, -6, 3, 600};

Use range based for:

nums = getKLeastNumbers(nums, 1);

for(int i=0; i&lt;nums.size(); i++)
{
    std::cout&lt;&lt;nums.at(i)&lt;&lt;std::endl;
}


becomes

for (auto &amp;i : getKLeastNumbers(nums, 1))
    std::cout &lt;&lt; i &lt;&lt; '\n';

Do not hide bugs. If you detect that someone used your function wrong tell them instead of letting them wonder why the return value doesn't make sense.

if(k&lt;=0 || k &gt; nums.size())
{
    return tmpNums;
}


becomes

assert(k &lt;= 0 &amp;&amp; k &gt; nums.size());


or

if (k &lt;=0 || k &gt; nums.size())
    throw std::range_error("k must be bigger than 0 and less than num's size");

You seem to be using the heap functions correctly, however, there are functions more suitable for that. I would pick std::partial_sort.

std::vector&lt;int&gt; getKLeastNumbers(std::vector&lt;int&gt; &amp;nums, int k)
{
    std::partial_sort(std::begin(nums), std::begin(nums) + k, std::end(nums));
    return { std::begin(nums), std::begin(nums) + k };
}

The declaration for getKLeastNumbers is a bit strange. nums is not const and gets modified which feels unexpected. Why can I not use getKLeastNumbers on a const std::vector?. I would prefer a const &amp; to preserve the original value, allow const vector and to be able to initialize nums with an initializer list directly.