jariasf03
BAN USERAssuming the order of the output does not matter.
C++
space: O(n)
time complexity: O(n)
struct Hotel{
int hotel_id, user_id, score;
Hotel(){}
Hotel( int _hotel_id, int _user_id, int _score){
hotel_id = _hotel_id;
user_id = _user_id;
score = _score;
}
};
vector<int> get_hotels(vector<Hotel> scores, float min_avg_score ){
unordered_map<int,pair<int,int> > hash;
unordered_map<int,pair<int,int> > :: iterator it;
vector<int> hotels;
int sz = scores.size();
for( int i = 0 ; i < sz ; ++i ){
hash[ scores[i].hotel_id ].first+=scores[i].score;
hash[ scores[i].hotel_id ].second++;
}
for( it = hash.begin(); it != hash.end() ; ++it ){
pair<int,int> values = it -> second;
float avg_current = values.first/(float)(values.second);
if( avg_current >= min_avg_score )
hotels.push_back(it -> first );
}
return hotels;
}
If order matters then it will be possible by changing the hash with a map. Time complexity will be O(nlogn) though.
- jariasf03 July 08, 2016
In-place solution.
- jariasf03 July 15, 2016