### MahmoudSayed's blog

By MahmoudSayed, 9 years ago,

There are 1 billion stars and you are standing at earth. Form the earth you know the distance of all 1 billion stars. Find the nearest 1 million stars from the earth.

•  » » 9 years ago, # ^ | ← Rev. 2 →   +1 Firstly, I wanna thank you for your comment. Secondly, 1 billion is still a large number to store it in an array So i thought about another solution and I found this one out Using Binary Search Tree. While reading the input I will insert the current number(distance) to the tree.when the size of the tree is larger than 1 million I will delete the largest one and insert the current element(only if the current element is smaller than the largest one in the tree) otherwise ignore this number.Finally the tree has the the nearest 1 million stars and I can print them. while(cin >> n ) { if(NumberOfElementsInTheTree > int(1e6)) { if(n > TheLargestElementInTheTree) continue; else Delete(TheLargestElementInTheTree); } Insert(n); } Cause I'm newbie with the Binary Search Tree I think this algorithm's complexity will be O(nlog(n)) (Without printing)I dunno if This algorithm and its complexity are right or not.
•  » » » 9 years ago, # ^ |   +3 vector v for value in input: v.push_back(value) if v.size >= 2 * k: nth_element(v) //remove all elements except first k nth_element(v) //remove all elements except first k //v contains k nearest points here  Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less. http://www.cplusplus.com/reference/algorithm/nth_element/