tag:blogger.com,1999:blog-6314876008291942531.post5217659929640223415..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Find top log(n) or top sqt(n) values in an array of integersUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6314876008291942531.post-71753918330351075562011-05-31T04:17:29.712-07:002011-05-31T04:17:29.712-07:00If k=0, then it's easy - you just output an em...If k=0, then it's easy - you just output an empty set.<br /><br />If k>0, then the problem is at least as difficult as finding the 1 top element.<br /><br />I am not sure if "top" means "most frequent" or "highest value", but in both cases you need to read all elements to be sure that your answer is right.<br /><br />Example ("most frequent"): a small number of 1s, the same large number of 2s and 3s, and one unknown integer x.<br /><br />Example ("highest value"): all elements equal to 10, except one unknown.Anonymoushttps://www.blogger.com/profile/16234740155371832738noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-84631011380820650492011-05-31T02:15:04.263-07:002011-05-31T02:15:04.263-07:00and if you need to find the top k?and if you need to find the top k?codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-6800822329439451152011-05-29T12:50:12.345-07:002011-05-29T12:50:12.345-07:00I am lost here. Are we talking about worst-case si...I am lost here. Are we talking about worst-case single-threaded asymptotic time complexity?<br /><br />I think it has to be at least O(n), because missing even a single entry in the array can alter the result.<br /><br />What am I missing this time? :)Anonymoushttps://www.blogger.com/profile/16234740155371832738noreply@blogger.com