Short easy C++ using set





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



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

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

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

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

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