dskut
BAN USERIn fact you don't need a heap or a binary search tree here, because all the array is already loaded into memory. So you can use some modification of Quick-Select algorithm, to achieve O(n) speed and O(1) extra-memory (because tail recursion can be effectively eliminated) in case you don't need your initial array later on
See wikipedia for "Selection_algorithm" and "Partial_sorting"
Actually, one would need a heap, if
1) points are not yet loaded, and you receive them one-by-one (i.e. it's not a set of points, but a stream)
2) or maybe you are out of memory, and you have to preserve the initial array (quickselect-based algoritm would modify it) - then you can use heap with O(k) memory instead of O(n) copy of array
So here is my C++ solution of finding k largest nums in the array - one can easily modify it to work with points and distances. To eliminate worst case one should also randomize selecting pivot
#include <vector>
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
// partition descending
size_t Partition(vector<int>& v, size_t start, size_t end) {
int i = start;
for (size_t j = start; j < end; ++j) {
if (v[j] > v[end]) {
swap(v[j], v[i]);
++i;
}
}
swap(v[i], v[end]);
return i;
}
vector<int> FindKLargestInArray(vector<int>& v, size_t start, size_t end, int k) {
if (end <= start) {
if (k == 0) {
return vector<int>(1, v[start]);
} else {
return vector<int>();
}
}
size_t pivot = Partition(v, start, end);
size_t pivotRelative = pivot - start;
if (pivotRelative > k) {
return FindKLargestInArray(v, start, pivot - 1, k);
} else if (pivotRelative < k) {
vector<int> res(v.begin() + start, v.begin() + pivot + 1);
vector<int> rightRes = FindKLargestInArray(v, pivot + 1, end, k - pivotRelative - 1);
res.insert(res.end(), rightRes.begin(), rightRes.end());
return res;
} else {
return vector<int>(v.begin() + start, v.begin() + pivot + 1);
}
}
/***********************************************/
ostream& operator<<(ostream& o, const vector<int>& v) {
for (size_t i = 0; i < v.size(); ++i) {
o << v[i] << " ";
}
return o;
}
vector<int>& operator+=(vector<int>& v, int x) {
v.push_back(x);
return v;
}
vector<int>& operator,(vector<int>& v, int x) {
v.push_back(x);
return v;
}
int main() {
srand(time(NULL));
vector<int> v;
v += 0, 1, 2, 2, 3, 4, 4, 6, 8, 8, 8, 9, 10,
11, 12, 12, 14, 15, 17, 19, 20;
random_shuffle(v.begin(), v.end());
int k = 4; // in interface count k from 1, but in implementation count k from 0
cout << v << endl;
vector<int> largest = FindKLargestInArray(v, 0, v.size() - 1, k - 1);
sort(largest.begin(), largest.end()); // optional
cout << largest << endl; // 15, 17, 19, 20
return 0;
}
Did they want some optimized solution (KMP/Rabin-Karp/FA)? Or you could just use a naive approach?
- dskut March 21, 2013