Median
https://www.hackerrank.com/challenges/median
Test cases: https://s3.amazonaws.com/hr-testcases/104/input01.txt
(input00.txt to input09.txt)
This is a classic problem: finding the moving median for an integer stream. The key idea is to use two ordered structures (one for the smaller half and another for the larger half). If we can make sure that these two half are size-balanced, we can easily obtain the median.
Remarks:
1. If the delete operation is not required, priority_queue could be used. Here I use multiset to implement add/remove/search in O(logn). Find median is O(1). Note that instead of using set, multiset should be used for handling duplicated values.
2. multiset<int, greater<int> > defines a multiset in descending order. In this case, the begin() iterator points to the largest number. On the other hand, multiset<int, less<int> >, which is by default, defines a multiset in ascending order.
3. I spend a lot of the times on the output format for cout... This problem requires that the integers are outputted without any zero after the decimal point; the double values are outputted without extra zeros after the decimal point. Now I use
cout << fixed << setprecision(1)
"fixed" means that we do not use scientific expressions. "setprecision", which is defined in "iomanip", is used to set the precision. Is there any better way to achieve this?
Test cases: https://s3.amazonaws.com/hr-testcases/104/input01.txt
(input00.txt to input09.txt)
This is a classic problem: finding the moving median for an integer stream. The key idea is to use two ordered structures (one for the smaller half and another for the larger half). If we can make sure that these two half are size-balanced, we can easily obtain the median.
Remarks:
1. If the delete operation is not required, priority_queue could be used. Here I use multiset to implement add/remove/search in O(logn). Find median is O(1). Note that instead of using set, multiset should be used for handling duplicated values.
2. multiset<int, greater<int> > defines a multiset in descending order. In this case, the begin() iterator points to the largest number. On the other hand, multiset<int, less<int> >, which is by default, defines a multiset in ascending order.
3. I spend a lot of the times on the output format for cout... This problem requires that the integers are outputted without any zero after the decimal point; the double values are outputted without extra zeros after the decimal point. Now I use
cout << fixed << setprecision(1)
"fixed" means that we do not use scientific expressions. "setprecision", which is defined in "iomanip", is used to set the precision. Is there any better way to achieve this?
Comments
Post a Comment