Short easy C++ using set


  • 31

    Track the largest three values in a set.

    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for (int num : nums) {
            top3.insert(num);
            if (top3.size() > 3)
                top3.erase(top3.begin());
        }
        return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
    }
    

    Alternatively (not sure which one I like better):

    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for (int num : nums)
            if (top3.insert(num).second && top3.size() > 3)
                top3.erase(top3.begin());
        return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
    }

  • 1
    S

    std::set usually uses a red-black tree, so wouldn't this be nlogn?


  • 1

    @sean46 Depends on what you mean with "nlogn".


  • 10
    W

    Since we only have 3 elements, insert/delete is constant time operations. Don't stick to O(nlog n) concept. We only care about big O when the things we are dealing with is big.


  • 1
    O

    I got the same idea using python:

    class Solution(object):
        def thirdMax(self, nums):
            l = []
            for n in set(nums):
                bisect.insort(l, -n)
                if len(l)>3:
                    l.pop()
            return -l[2] if len(l)>2 else -l[0]
    

  • 1

    @o_sharp Could also use

            bisect.insort(l, -n)
            del l[3:]
    

    or

            l = sorted(l + [-n])[:3]

  • 0

    My HashSet approach in Java, though not good in performance(25ms):

    public int thirdMax(int[] nums) {
    	Set<Integer> s = new HashSet<Integer>();
    	int max = nums[0];
    	int left = max;
    	for(int num : nums){
    		//push into set
    		s.add(num);
    		//update max
    		if(max < num) max = num;
    		//keep track min in set
    		if(s.size() <= 3){
    			left = Math.min(num, left);
    		}
    		else{
    			s.remove(Math.min(left, num));
    			left = Math.max(left,num);
    	    	for(int setNum : s){
    	        	left =Math.min(setNum, left);
            	}
    		}
    	}
    
    	return s.size()<3 ? max:left;
    }
    

    Please tell me if there is any improvement in my code


  • 3
    B

    Same solution in Java, runs in 20ms.

    public class Solution {
      public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int num : nums) {
          set.add(num);
          if(set.size() > 3) {
            set.remove(set.first());
          }
        }
        return set.size() < 3 ? set.last() : set.first();
      }
    }
    

  • 0
    W
    This post is deleted!

  • 0
    J

    @StefanPochmann said in Short easy C++ using set:

    Track the largest three values in a set.

    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for (int num : nums) {
            top3.insert(num);
            if (top3.size() > 3)
                top3.erase(top3.begin());
        }
        return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
    }
    

    Alternatively (not sure which one I like better):

    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for (int num : nums)
            if (top3.insert(num).second && top3.size() > 3)
                top3.erase(top3.begin());
        return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
    }

  • 0
    M

    I used the same solution and it costs 9ms.
    Then I reduced the time to 6ms by avoiding some sorting...

        int thirdMax(vector<int>& nums) {
            set<int> top3;
            for (int num : nums)
            {
                if (top3.size() < 3 || num > *top3.begin())
                    top3.insert(num);
                if (top3.size() > 3)
                    top3.erase(top3.begin());
            }
            return (top3.size() < 3) ? *top3.rbegin() : *top3.begin();
        }
    

  • 0
    K

    @StefanPochmann

    I don't think using a set in the way that you are in your solution is consistent with the spirit of this question. Here's my 3n, 10 ms approach in Java:

    public int thirdMax(int[] nums) {
            Integer[] maxs = new Integer[3];
            for (int num : nums) {
                int candidate = num;
                for (int i = maxs.length - 1; i >= 0; i --) {
                    if (maxs[i] == null) {
                        maxs[i] = candidate;
                        break;
                    } else if (candidate > maxs[i]) {
                        int tmp = maxs[i];
                        maxs[i] = candidate;
                        candidate = tmp;
                    } else if (candidate == maxs[i]) {
                        // avoid duplicates
                        break;
                    }
                }
            }
            return maxs[0] != null ? maxs[0] : maxs[2];
        }
    

  • 0

    @knowledge2thepeople said in Short easy C++ using set:

    I don't think using a set in the way that you are in your solution is consistent with the spirit of this question.

    Why not?


  • 0
    K

    @StefanPochmann I signed back on just now to retract my statement. I was confused when I wrote my original comment last night. Your solution is good. If I'm correct, it runs in n * log(3) time, which is linear.


Log in to reply
 

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