LeetCode-414-第三大的数

第三大的数

题目描述:给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:使用优先队列

首先,初始化一个优先队列PriorityQueue为queue,然后遍历nums中的元素,遍历过程如下:

  • 如果当前元素已经在queue中,则跳过,否则将当前元素添加到queue中;
  • 如果queue的元素数量大于3,则从queue中移除一个元素(溢出的元素为最小的)。

遍历完成后,如果queue只有3个元素,则取出queue中的第一个元素并返回,即为nums中第三大的元素;如果queue没有3个元素,则取出最后一个元素返回即为nums中的最大元素并返回。

import java.util.PriorityQueue;

/**
 * @Author: ck
 * @Date: 2021/9/29 8:08 下午
 */
public class LeetCode_414 {
    /**
     * 使用优先队列
     *
     * @param nums
     * @return
     */
    public static int thirdMax(int[] nums) {
        PriorityQueue queue = new PriorityQueue(3);
        for (int num : nums) {
            // 重复的元素过滤掉
            if (!queue.contains(num)) {
                queue.add(num);
            }
            // 因为获取的是第三大的元素,所以当queue中的元素数量超过3时,需要将当前最小的元素取出
            if (queue.size() > 3) {
                queue.poll();
            }
        }
        if (queue.size() == 3) {
            // 当queue只有3个元素时,取最小的即为第三大的元素
            return queue.peek();
        } else {
            // 当queue的元素数量不够3个时,遍历queue取最大的一个
            int max = -1;
            while (!queue.isEmpty()) {
                max = queue.poll();
            }
            return max;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 2, 5, 3, 5};
        System.out.println(thirdMax(nums));
    }
}
【每日寄语】 生命的意义在于燃烧自己的同时能否照亮自己。

你可能感兴趣的