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)
@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.
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)
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?
@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.
@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
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.
@mlaw0 Awesome! And thanks
@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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.