I solve problems to prepare for interviews. Now I have written the algorithm of finding K largest numbers in array. Various solutions are described here: https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/. Initially, I came up with the solution myself and looks my solution corresponds to that described as Method 2 on the site, with the difference that I additionally use the "old minimum" to cut off unnecessary steps along the nested loop.
What could be written better in my code? What could be used instead of pmin
?
Here is my implementation:
using namespace std;
vector<int> largest_part_of_vector(const vector<int>& vec, int K_PartSize)
{
assert(K_PartSize < vec.size());
vector<int> ret(K_PartSize);
// Initial filling of temporary vector
int ind = 0; // main end-to-end index
int* pmin = const_cast<int*>(&vec[0]); // current minimum
// How `pmin` could be declared and used better?
for (auto& elemRef : ret)
{
elemRef = vec[ind];
if (elemRef < *pmin)
{
pmin = &elemRef; // pmin is from `vecPart` now and will not modify `vec`
}
ind++;
}
// the rest part
auto oldMin = *pmin;
for (; ind < vec.size(); ind++)
{
auto v = vec[ind];
if (v > oldMin) // preliminary check to avoid unnecessary checks
{
for (auto& elemRef : ret)
{
if (elemRef < *pmin)
{
pmin = &elemRef;
}
}
if (v > * pmin)
{
oldMin = *pmin;
*pmin = v;
}
}
/*else
{
savedIterations++;
}*/
}
return ret; // As I understand, moving operator=( vector&& other ) will be used here
}
std::partial_sort_copy
. \$\endgroup\$