- 27.9%
https://leetcode.com/problems/third-maximum-number/
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
1 | Example 1: |
1 | Example 2: |
1 | Example 3: |
https://discuss.leetcode.com/topic/63903/short-easy-c-using-set
方法一:
Short easy C++ using set
Track the largest three values in a set.
1 | int thirdMax(vector<int>& nums) { |
我的代码实现:
主要几点,set是有序的,set可以去重。erase函数用法,对于地址的解析。begin, rbegin函数。
1 | class Solution { |
Alternatively (not sure which one I like better):
1 | int thirdMax(vector<int>& nums) { |
python
https://discuss.leetcode.com/topic/64696/a-python-amusing-solution-which-actually-beats-98
A python amusing solution, which actually beats 98%…
1 | def thirdMax(self, nums): |
https://discuss.leetcode.com/topic/70613/intuitive-and-short-python-solution
Intuitive and Short Python solution
Time complexity is O(n), space complexity is O(1).
1 | class Solution(object): |
https://discuss.leetcode.com/topic/63962/python-2-5-lines-o-n-time-o-1-space
Python: 2-5 lines, O(n) time, O(1) space
1 | def thirdMax(self, nums): |
A slightly shorter but uglier version based on the same concept is:
Although I’m not sure whether the second version is still O(1) space. Does anyone know whether the Python interpreter will create the whole list comprehension in memory even though it is not being assigned anywhere?
Update: two line solution by @StefanPochmann below.1
2
3
4def thirdMax(self, nums):
l = [float('-inf')] * 3
[heapq.heappushpop(l, n) for n in nums if n > l[0] and n not in l]
return l[0] if l[0] != float('-inf') else max(l)
java
https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1
Java PriorityQueue O(n) + O(1)
1 | public class Solution { |
Nice solution, and here is the concise version:
1 | public class Solution { |
https://discuss.leetcode.com/topic/62236/java-solution-in-0ms-run-time-o-n-and-space-o-1
Java solution in 0ms run time O(n) and space O(1).
1 | public int thirdMax(int[] nums) { |
https://discuss.leetcode.com/topic/63671/o-n-time-o-1-space-java-short-solution
O(n) time O(1) space Java short solution
1 | public class Solution { |
https://discuss.leetcode.com/topic/65119/java-solution-using-treeset
Java Solution Using TreeSet
1 | public class Solution { |