Question
Given a non-empty array of integers, return the third maximum number in this array. If it does not exists, return the maximum number. The time complexity must be in O(n).
Note
- 設(shè)置3個(gè)臨時(shí)變量侥袜，分別存儲(chǔ)max1, max2, max3。也可以是一個(gè)長(zhǎng)度為3的數(shù)組矗晃。
Extension
- 求第k大的數(shù)（k < 5, k值變大，求解效率變低宴倍。）张症，都可以使用這個(gè)方法來(lái)求解。
- 堆排序雛形鸵贬。求第k大（兴姿），可以建立k長(zhǎng)的大頂堆（小頂堆）阔逼。
- Java中兆衅，PriorityQueue是用數(shù)組的形式實(shí)現(xiàn)了二叉小頂堆。
Solution
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;
}
// 注：此解法非原創(chuàng)嗜浮，只供提供學(xué)習(xí)思路羡亩。
