/**
 * Created by wanlipeng on 2017/4/18.
 */

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function (nums) {
    function sort(arr) {
        arr.sort(function (a, b) {
            return a - b;
        })
    }
    var m = new Array();
    for (var i in nums) {
        if (m.indexOf(nums[i]) >= 0) { // 如果已经存在，则略过
            continue;
        }
        if (m.length < 3) {
            m.push(nums[i])
        } else {
            if (nums[i] > Math.min.apply(null, m)) {
                m.push(nums[i])
                sort(m)
                m.shift()
            }
        }
    }
    sort(m)
    if (m.length < 3) {
        return Math.max.apply(null, m);
    }
    return m[0];
};

// Test case
console.log(thirdMax([3, 2, 1]))
console.log(thirdMax([2, 2, 3, 1]))
Add 414 Third Maximum Number