public class Solution {
public int thirdMax(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.contains(i)) {
pq.offer(i);
set.add(i);
if (pq.size() > 3) {
set.remove(pq.poll());
}
}
}
if (pq.size() < 3) {
while (pq.size() > 1) {
pq.poll();
}
}
return pq.peek();
}
}
Java PriorityQueue O(n) + O(1)


Nice solution, and here is the concise version:
public class Solution { public int thirdMax(int[] nums) { PriorityQueue<Integer> pq = new PriorityQueue<>(); Set<Integer> set = new HashSet<>(); for(int n : nums) { if(set.add(n)) { pq.offer(n); if(pq.size() > 3 ) pq.poll(); } } if(pq.size() == 2) pq.poll(); return pq.peek(); } }




@potpotpot inserting element to a heapq takes log(n), and removingMin from a heapq also takes log(n), so here we should expect n2log(3) time complexity.

No need to use set besides priority_queue. Just use a counter. Here is c++ code:
int thirdMax(vector<int>& nums) { priority_queue<int> pq(nums.begin(), nums.end()); int maxNum = pq.top(), res = pq.top(); int count = 1; while (!pq.empty() && count < 3) { int cur = pq.top(); pq.pop(); if (cur != res) { res = cur; count++; } } return count == 3 ? res : maxNum; }

Great solution, but could you please explain more about how priority queue here works? Probably because I don't know this structure well, does it maintain the data in it in an ascending way or descending way, or when it poll elements it picked the largest one or smallest one? Thank you.

@karolQ PriorityQ works by storing the elements in their natural order. In this case it is the ascending order of the integers. However you can specify your own ordering by using Comparator. poll removes the first element in the queue. So in this case it picks the smallest one which is at the front of the queue.


@songzec Great Logic. However, the run time is a little bit high.
Here is a faster one.public int thirdMax(int[] nums) { long b1 = 2147483649L; long b2 = 2147483649L; long b3 = 2147483649L; for(int i = 0; i < nums.length; i++){ if(nums[i] > b1){ b3 = b2; b2 = b1; b1 = nums[i]; } else if(nums[i] > b2 && nums[i] != b1){ b3 = b2; b2 = nums[i]; } else if(nums[i] > b3 && nums[i] != b2 && nums[i] !=b1){ b3 = nums[i]; } } if(b3 != 2147483649L ) return (int)b3; else return (int)b1; }

No need to have the set part since the queue will automatically pop it. Here is my code.
public class Solution { public int thirdMax(int[] nums) { PriorityQueue<Integer> pq= new PriorityQueue<Integer>(); for(int num: nums){ if(!pq.contains(num)){ pq.offer(num); set.add(num); if(pq.size()>3) pq.poll(); } } if(pq.size()<3){ while(pq.size()>1){ pq.poll(); } } return pq.peek(); } }

@leuction you are right, inserting an element into a heap with size n will cost O(logn), but in this case the heap.size() <= 4, not n, so the total time complexity is O(n)


Do let me know your thoughts on this.. It worked well
int x = nums.length; int p=0; int i=0; if(x<3) return nums[x1]; Arrays.sort(nums); int count=0; for(i=1 ;i<x;i++) { p=xi; if(nums[p]!=nums[p1]) { count++; } if (count==2){ break;} } if(count<2) { return nums[x1]; } return nums[p1];

@leuction definitely agree with your idea. it's not the log(n) method. the nlog(n) instead!