Java PriorityQueue O(n) + O(1)


  • 29
    S
    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();
        }
    }

  • 13

    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();
        }
    }
    

  • 1
    P

    @dilyar is the running time nlog(3)?


  • 0
    C

    @dilyar you should use pq.poll() instead of pq.remove(pq.poll())


  • 0

    @caocode Thanks for your suggestion. I have updated my code.


  • 3
    T

    @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.


  • 1
    P

    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;
    }

  • 0

    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.


  • 0
    M

    @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.


  • 0
    D
    This post is deleted!

  • 0
    Y

    //Since the time complexity of add() in priorityqueue is log(n), and we only consider the first three, so this part should be log3
    //contains() cost n, poll cost logn but does not happen very often, so the whole thing should be n^2log(3)


  • 0

    @mrutyunjaya Thanks!


  • 0
    Z

    @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;
    }

  • -1
    L

    insert a element into a heap, which is the priorityqueue will cost O(logn), the total time complexity is O(nlogn) instead, not O(n).


  • 0
    H

    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();
        }
    }
    

  • 2
    E

    @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)


  • 0
    J

    @hwmiku You missed to comment/remove the set. Or else it works good.

    set.add(num);


  • 0
    M

    you really did a great job!


  • 0
    L

    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[x-1];
            
            Arrays.sort(nums);
            int count=0;
            for(i=1 ;i<x;i++)
            {
              p=x-i;	
              if(nums[p]!=nums[p-1])
              {
            	  count++;
              }
    
              if (count==2){
            	break;}
            }
            if(count<2)
            {
                return nums[x-1];
            }
            
            
            return nums[p-1];
    

  • -2
    Y

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


Log in to reply
 

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