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.
I use sort and set to remove duplicate and rank
def thirdMax(self, nums): nums = list(set(nums)) nums.sort() if len(nums)<=2: return nums[-1] return nums[-3]
@duweimofashi list it and sort it does look better than max and remove, but python sort costs O(nlogn)
@mlaw0 Very cool. Thank you for sharing! I did overlook the fact that this could be done with no constraint on memory! Here's my solution with no memory. It managed to beat 78% of solutions
def thirdMax(self, nums): if len(nums) < 3: return max(nums); maxElem = - float("inf"); secondMax = - float("inf"); thirdMax = - float("inf"); for elem in nums: if elem == maxElem or elem == secondMax or elem == thirdMax: continue; if elem > maxElem: thirdMax = secondMax; secondMax = maxElem; maxElem = elem; elif elem > secondMax: thirdMax = secondMax; secondMax = elem; elif elem > thirdMax: thirdMax = elem; if thirdMax == -float("inf"): return maxElem; else: return thirdMax;
@mlaw0 I like it. I was afraid using
set will cost me a lot of time. Thank you for the time complexity explanation.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.