ThirdMaximumNumber [source code]
public class ThirdMaximumNumber {
static
/******************************************************************************/
public class Solution {
public int thirdMax(int[] nums) {
Integer first = null, second = null, third = null;
for (int i : nums) {
if (first == null || i >= first) {
if (first != null && first == i) continue;
third = second;
second = first;
first = i;
} else if (second == null || i >= second) {
if (second != null && second == i) continue;
third = second;
second = i;
} else if (third == null || i > third) {
third = i;
}
}
return third == null ? first : third;
}
}
/******************************************************************************/
public static void main(String[] args) {
ThirdMaximumNumber.Solution tester = new ThirdMaximumNumber.Solution();
int[][] inputs = {
{3,2,1}, {1},
{1,2}, {2},
{2,2,3,1}, {1},
{5,2,2}, {5},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] nums = inputs[2 * i];
int expected = inputs[1 + 2 * i][0];
System.out.println(Printer.seperator());
Printer.openColor("magenta");
System.out.print(Printer.array(nums));
Printer.closeColor();
int output = tester.thirdMax(nums);
System.out.print(" -> " + output);
Printer.openColor(output == expected ? "green" : "red");
System.out.println(", expected: " + expected);
Printer.closeColor();
}
}
}
题目本身其实挺简单的, 不过思路没有理清楚, 还是坑坑洼洼写了半天, 丢人好吧.
.equals并不能避免对null的检查: 也就是说一个null, 一个是比如1, 那么这两个用equals比较还是会报错;
最后的速度是5ms (81%), 一般般;
这个是submission最优解4(89):
public class Solution {
public int thirdMax(int[] nums) {
int length = nums.length;
if (length == 0) {
return -1;
}
if (length == 1) {
return nums[0];
}
if (length == 2) {
return nums[0] < nums[1] ? nums[1] : nums[0];
}
long first = Long.MIN_VALUE;
long second = Long.MIN_VALUE;
long third = Long.MIN_VALUE;
for (int i = 0; i < length; ++i) {
int c = nums[i];
if (c > first) {
third = second;
second = first;
first = c;
} else if (c > second) {
if (c != first) {
third = second;
second = c;
}
} else if (c > third) {
if (c != second) {
third = c;
}
}
}
return third == Long.MIN_VALUE ? (int) first : (int) third;
}
}
这个的思路还是很聪明的, 有点类似mergeSortedArray的时候的一个思路: 与其判断Null, 他这里的方法就是直接用sentinel的思路: 让算法可以自动处理uninitialized的情形;
这个是discussion上面跟我的类似的一个思路, 但是他简化了一些东西:
public int thirdMax(int[] nums) {
Integer max1 = null;
Integer max2 = null;
Integer max3 = null;
for (Integer n : nums) {
if (n.equals(max1) || n.equals(max2) || n.equals(max3)) continue;
if (max1 == null || n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (max2 == null || n > max2) {
max3 = max2;
max2 = n;
} else if (max3 == null || n > max3) {
max3 = n;
}
}
return max3 == null ? max1 : max3;
}
"相等"的情况直接丢弃, 这个是一样的想法;
但是他有一个很聪明的问题解决了我的想法: 他把iterator做成了Integer而不是int, 这样的话就可以使用equals了!!! int是没有equals这个method的; 另外注意这里他写的顺序:是n.equals(max1)而不是max1.equals(n), 因为n是始终不可能为Null的, 所以你dot of n始终是合法的;
If i were the interviewer I would ask "what is not ideal about this solution?"
And the answer I expect would be that it's not easily modifiable, for example if you want to find 7th maximum instead of 3rd.
I like the answers using dynamic data structures more because of that reason. (I used a linked list)
这个确实是实话, 因为这个代码一个很大的问题就是hardcode的部分很多, extensibility很差;
这个是另外一个思路:
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();
}
}
当然set的这些API我也是不知道, 居然还可以直接按照大小排序的get;
不过这个代码最后的速度其实非常不好: 20. 可能set的这个大小排序实际上实现的并不好, 毕竟当时看书的时候也没记得set对于这种排序get有什么特别的优势;
不过他们认为, 这个set我们几让控制在size只有3, 那么实际上排序速度是完全不需要担心的;
这个是另外一个有extensiblity的版本:(上面set的其实也是extensible的)
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();
}
}
这个是一个简写之后的版本:
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();
}
也就是set就完全是一个用来ignore duplicate的作用; 这个人的一个改进就是当size超了之后, 原来的代码是除了pq要Poll掉一个, set也要remove一个, 但是实际上set的这个remove是没有必要的: 已经被淘汰过一次的num, 是不可能再进入pq的, 所以在set里面留着他也没有影响;
这个是一个不使用set的版本:
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;
}
priorityqueue本身insert和remove的复杂度都是lgN, 但是因为这里实际上N控制的很小, 就都可以认为是O(1); 这种点感觉在面试当中也不是不会考到;
Problem Description
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
Difficulty:Easy
Total Accepted:36.8K
Total Submissions:132.4K
Contributors:
ZengRed , 1337c0d3r
Companies
amazon
Related Topics
array
Similar Questions
Kth Largest Element in an Array