Third Maximum Number

Leave a comment

November 7, 2016 by oneOokay

PriorityQueue + Set

我是用了一个size为n的priority queue max on top:

  • 注意写priorityQueue的Comparator
  • Set的初始化

可以优化为priority queue里只放4个元素,节省空间。

public int thirdMax(int[] nums) {
Queue<Integer> queue = new PriorityQueue(nums.length, Collections.reverseOrder());
//reverseOrder()之后有括号。
Set<Integer> set = new HashSet<Interger>();
for (int i = 0; i < nums.length; i ++){
if (set.contains(nums[i])){
continue;
}
queue.offer(nums[i]);
set.add(nums[i]);
}
if (queue.size() < 3){
return queue.poll();
}
int result = 0;
for (int i = 0; i < 3; i ++){
if (!queue.isEmpty()){
result = queue.poll();
}
}

return result;
}


Besides: comparator
Queue<Integer> queue = new PriorityQueue<Integer>(size, new Comparator<Integer>(){
//Comparator<T>(): Comparator<T>()后面也有括号
public int compare(int a, int b){
if (a > b){
return -1;
}
if (a < b){
return 1;
}
return 0;
}});

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: