farzad
BAN USER{{
//dpCount: keeps track of minimum number of coins as the value of key in hashmap
//coins: is a vector of available coins
int nCoins(int S, map<int, int> &dpCount, vector<int> &coins)
{
int retVal = -1;
for (size_t i = 0; i < coins.size(); i++){
if (coins[i] <= S){
int postSum = S-coins[i];
if (dpCount.find(postSum) == dpCount.end()){
dpCount[postSum] = nCoins(postSum, dpCount, coins);
}
if (dpCount.find(S) == dpCount.end()){
dpCount[S] = dpCount[postSum] + 1;
}
else{
dpCount[S] = min(dpCount[S], dpCount[postSum] + 1);
}
}
}
return dpCount[S];
}
Time complexity: O(N + N log K)
void firstKPoints(multimap<int, int> &twoDpoints, size_t k, multimap<int, int> &kpoints)
{
multimap<float, map<int,int> > distKey;
//compute distance
for (multimap<int, int>::iterator it = twoDpoints.begin(); it != twoDpoints.end(); it++){
if (it->first > (int)k || it->second > (int)k)
continue;
float dist = sqrt(pow((float)it->first, (float)2.0)+pow((float)it->second, (float)2.0));
map<int,int> pnt;
pnt[it->first] = it->second;
distKey.insert(pair<float,map<int,int> >(dist, pnt));
}
//use limited size heap to sort distance
priority_queue<float> heapK;
for (multimap<float, map<int,int> >::iterator it = distKey.begin(); it != distKey.end(); it++){
float dist = it->first;
heapK.push(dist);
if (heapK.size() > k){
heapK.pop();
}
}
//output points
int pnum = 0;
while (!heapK.empty()){
pair<multimap<float,map<int,int> >::iterator,multimap<float,map<int,int> >::iterator> keyRange = distKey.equal_range(heapK.top());
for (multimap<float,map<int,int> >::iterator it = keyRange.first; it != keyRange.second; it++){
kpoints.insert(pair<int,int>(it->second.begin()->first, it->second.begin()->second));
pnum++;
if (pnum == k){
return;
}
heapK.pop();
}
}
}
- farzad July 09, 2012