Created
June 13, 2018 08:48
-
-
Save applenob/38561d91859a632922930570da1560a7 to your computer and use it in GitHub Desktop.
Keep top n number in a list with ascend order.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class TopQueue: | |
"""keep top n num in a list with ascend order.""" | |
def __init__(self, n): | |
self.n = n | |
self.queue = [] | |
def add(self, new_val): | |
bigger_index = -1 | |
for i, one in enumerate(self.queue): | |
if one > new_val: | |
bigger_index = i | |
break | |
if bigger_index == -1: | |
# no one in the queue is bigger than the new val | |
if len(self.queue) == self.n: | |
del self.queue[0] | |
self.queue.append(new_val) | |
return True | |
if bigger_index == 0: | |
# the first one in the queue is bigger than the new val | |
if len(self.queue) == self.n: | |
return False | |
self.queue.insert(0, new_val) | |
return True | |
else: | |
# someone in the queue is bigger than the new val | |
if len(self.queue) == self.n: | |
del self.queue[0] | |
self.queue.insert(bigger_index - 1, new_val) | |
else: | |
self.queue.insert(bigger_index, new_val) | |
return True | |
def get_queue(self): | |
return self.queue | |
def test_TopQueue(): | |
tq = TopQueue(3) | |
print(tq.add(1)) | |
print(tq.get_queue()) | |
print(tq.add(0)) | |
print(tq.get_queue()) | |
print(tq.add(2)) | |
print(tq.get_queue()) | |
print(tq.add(3)) | |
print(tq.get_queue()) | |
print(tq.add(2)) | |
print(tq.get_queue()) | |
print(tq.add(3)) | |
print(tq.get_queue()) | |
print(tq.add(3)) | |
print(tq.get_queue()) | |
print(tq.add(1)) | |
print(tq.get_queue()) | |
print(tq.add(4)) | |
print(tq.get_queue()) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment