414. 第三大的数

[bitfishxyz]

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

[bitfishxyz]

解析

这题看起起来简单，其实要考虑各种情况，综合起来挺复杂的。

为了方便，可以专门的写一个新的数据结构。

[bitfishxyz]

Java

import java.util.Arrays;
import java.util.Set;

class Solution {
    /**
     * 构造一个新的数据结构，来存储前三大的数字
     */
    private class ThisSet {
        /**
         * 数据结构的容量，在[0, 3] 之间
         */
        private int size = 0;

        /**
         * 底层数组，当容量小于3时，这个数组后面的元素将被忽略
         */
        private int[] arr = new int[3];

        /**
         * 获得当前数组中的最小值的索引
         * @return
         */
        private int getIndexOfMinValue(){
            assert size > 0;

            int minIndex = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] < arr[minIndex]){
                    minIndex = i;
                }
            }
            return minIndex;
        }

        /**
         * 看看这个数据结构中是否包含了目标值
         * @param thisValue
         * @return
         */
        private boolean contains(int thisValue){
            for (int i = 0; i < size; i++) {
                if (arr[i] == thisValue){
                    return true;
                }
            }
            return false;
        }

        /**
         * 这个数据结构的特点就是插入时不维护数组的有序性，需要的时候再排序
         * @param newValue
         */
        public void add(int newValue){
            // 数组中已经存在对应元素了，忽略这次插入
            if (contains(newValue)){
                return;
            }

            if (size < 3){
                arr[size] = newValue;
                size++;
            } else {
                int indexOfMinValue = getIndexOfMinValue();
                arr[indexOfMinValue] = Math.max(arr[indexOfMinValue], newValue);
            }
        }

        /**
         * 这个数组的最小值就是第三大的元素
         * @return
         */
        public int getThirdValue(){
            if (size == 0) {
                throw new RuntimeException("没有元素");
            }
            if (size == 1) {
                return arr[0];
            }
            if (size == 2) {
                return Math.max(arr[0], arr[1]);
            }

            return arr[getIndexOfMinValue()];
        }
    }

    public int thirdMax(int[] nums) {
        ThisSet set = new ThisSet();

        for (int value : nums) {
            set.add(value);
        }

        return set.getThirdValue();
    }
}