1 line python solution


  • -16

    It's straightforward, sort and pick.

    return sorted(nums)[-k]
    

    Just for fun.

    Are you seriously think that it's possible to implement Quickselect in one line?


  • 0
    S

    Instead of giving another down vote, I think it's beter to tell you why this is not acceptable. Because sorting takes O(nlogn) already. We're looking at an algorithm that aims at an average case of O(n). Quick select is the solution. Since quick select comes from quicksort, the worst case is still O(n^2). It is still an open topic for an algorithm to find top kth element at O(n) for the worst case.


  • 0

    The solution is just for fun. Are you seriously think that it's possible to implement Quickselect in one line?


  • 1

    @xcv58 Yes, it is possible :-P

    @sleepNull What do you mean, O(n) worst case is still an open topic?


  • 0

    Almost every algorithm can be ONE-LINE :)


  • 0

    Ha, yeah, maybe. I recently saw a stackoverflow question asking about exactly that for Python, but I don't remember the answers and I can't find it anymore. In Python it might be harder than in other languages, though, since you can't just dump arbitrary lines into one line like you can in C++ & Co. On the other hand, Python has powerful stuff making it easier...


  • 0
    Y

    That was similar of my submission. Turned out pretty fast. I guess the test cases are not in large arrays. But the O(nlogn) is killing this.


  • 0

    As I said, just for fun. In reality, the k may be changed by time or different function call if it's hot spot, so every time call an Quickselect and get O(n)*called_times. It's far more worse than keep in order and get O(1)*called_times performance. If it's not hot spot, who care it's O(n) or O(n log(n)).


  • 0
    Y

    You are right, if the array is static. However, in real case, say your api wants to check top 5 tweets at the time stamp, which are constantly changing, you can't afford to do sorting and selecting.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.