Saturday, September 17, 2011 No. 05 - The Least k Numbers Question: Please find out the least k numbers out of n numbers. For example, if given the 8 numbers 4, 5, 1, 6, 2, 7, 3 and 8, please return the least 4 numbers 1, 2, 3 and 4. Analysis: The naïve solution is sort the n input numbers increasingly, and the least k numbers should be the first k numbers. Since it needs to sort, its time complexity is O(nlogn). Interviewers will ask us explore more efficient solutions. Solution 1: O(nlogk) time efficiency,
Read full article from Coding Interview Questions: No. 05 - The Least k Numbers
No comments:
Post a Comment