Link to pdf version on UVa OJ
The problem statement is straightforward. A queue needs to be implemented.
What happened on my mind : the straightforward solution was somehow obvious to me from the beginning. We have a queue and in each iteration of the queue at least one number will be printed. So it would be of O(n^2) if I just implement what has been asked.
But I was looking for a better answer, some O(n) answer, I still think it exists, but I didn't figured it out yet, just a bunch of simple facts. All numbers less than X can be ignored, all numbers greater than X will be printed before X. If there are no other numbers equal to X the answer would be count of numbers greater than X plus one. But the tricky part is the other numbers equal to X.
Another simple fact, if we bunch consecutive X's together (ignoring number smaller than X), the order of print in a bunch is increasing.
After some thinking I decided to implement the straightforward solution.
I handled it with a simple queue and a frequency array. Another simple fact that helps implementing this solution is that if we have five 9's, four 8's, first all of five 9's will be printed, then the four 8's.
I check the front element of the queue, if it's value is equal to the maximum I throw it away and decrease count of Max by one. Whenever count of Max is equal to zero I move on to the next Max that still has frequency greater than zero.
Whenever I face the index I was looking for, I break and print the result.
Please refer to my code on github for more details.
The problem statement is straightforward. A queue needs to be implemented.
What happened on my mind : the straightforward solution was somehow obvious to me from the beginning. We have a queue and in each iteration of the queue at least one number will be printed. So it would be of O(n^2) if I just implement what has been asked.
But I was looking for a better answer, some O(n) answer, I still think it exists, but I didn't figured it out yet, just a bunch of simple facts. All numbers less than X can be ignored, all numbers greater than X will be printed before X. If there are no other numbers equal to X the answer would be count of numbers greater than X plus one. But the tricky part is the other numbers equal to X.
Another simple fact, if we bunch consecutive X's together (ignoring number smaller than X), the order of print in a bunch is increasing.
After some thinking I decided to implement the straightforward solution.
I handled it with a simple queue and a frequency array. Another simple fact that helps implementing this solution is that if we have five 9's, four 8's, first all of five 9's will be printed, then the four 8's.
I check the front element of the queue, if it's value is equal to the maximum I throw it away and decrease count of Max by one. Whenever count of Max is equal to zero I move on to the next Max that still has frequency greater than zero.
Whenever I face the index I was looking for, I break and print the result.
Please refer to my code on github for more details.
No comments:
Post a Comment