A python amusing solution, which actually beats 98%...


  • 24
    def thirdMax(self, nums):
            nums = set(nums)
            if len(nums) < 3:
                return max(nums)
            nums.remove(max(nums))
            nums.remove(max(nums))
            return max(nums)
    

  • 1
    Y

    this is really cool but I don't know if it exceeds the O(n) limitation


  • 0

    @YaoshuaiZhang So, converting a list to set costs O(n), taking max of a set costs O(n), removing an element from a set cost O(1) on average, so this code still runs in O(n).

    Surprisingly, this code beats 98%. I guess the test cases are either very weak or have a lot of duplicates.


  • 1
    L

    Well if the interviewer asks for the 1000th maximum or however large. You might want an answer you can scale (though I like what you did)

    class Solution(object):
        def thirdMax(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            a=[]
            for i,c in enumerate(nums):
                if len(a)<3 and c not in a:
                    a.append(c)
                else:
                    if c not in a and min(a)<c:
                        a[a.index(min(a))]=c
            return min(a) if len(a)>=3 else max(a)

  • 0

    I am Using The program below to test:

    import random as rand

    x=[]
    for _ in range(1,10002):
      x.append(rand.randint(1,5000))
    
    print x
    
    y=set(x)
    
    print y
    

    i found that the y is sorted, so if the set converting exceed the O(n) limitation?


  • 1

    @livelearn I don't really think your code scales better than what I had. If let's say we are looking for the M-th maximum,your algorithm will run with time complexity O(MN). In this case use a heap instead of list a will optimize time from O(MN) to O(NlogM), which is a more scalable option you are looking for.


  • 0

    @Huangyan9188 python set, or I think set in general, is unordered, elements are hashed.

    You are stuffing 10,001 random integers from [1,5000] to an array, so the elements inside the array will be very dense in the range [1,5000], by which I mean most elements in [1,5000] will show up in the array. In this case, the converted set will look "ordered" because of the way how python handles hash collisions in sets (http://stackoverflow.com/questions/12165200/order-of-unordered-python-sets).

    Change the range for the for loop to range(100) and y will not likely to be "sorted" anymore.

    Converting list to set is O(N) on average, and actually O(N^2) in the worst case, if you choose a very poor hash and collision happens every time you insert. In real life, hashes are carefully chosen, sets and hash table are usually considered to have O(1) time complexity for insertion. If you really worry about the O(N) limitation in the worst case, there are other great solutions using O(3) data structures to track max values, which yields a O(N) algorithm.


  • 0

    @mlaw0 Awesome! And thanks


  • 0
    B

    Smart solution!


  • 0
    L

    same with you. I want to look for more quickly algorithm


  • 0
    C

    @mlaw0 I think your complexity is k*n, which k is 3 in this case, n is the complexity of max(nums). I think the idea of this problem is to encourage to use quick sort or heap. But the problem is kind of vague.


  • -1
    C
    This post is deleted!

  • 0
    H

    one line solution

    return sorted(set(nums))[-3] if len(set(nums))>2 else max(nums)
    

Log in to reply
 

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