Leetcode刷题100天—414. 第三大的数( 数组)—day59

前言：

作者：神的孩子在歌唱

大家好，我叫智

414. 第三大的数

难度简单277收藏分享切换为英文接收动态反馈

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

提示：

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

进阶你能设计一个时间复杂度 O(n) 的解决方案吗？

package 数组;

import java.util.Arrays;
import java.util.Comparator;
/*
 * https://leetcode-cn.com/problems/third-maximum-number/
 * 思路：先排序，然后从后往前遍历，依次拿当前值跟最小值比较，如果小于就复制给min，知道取到第三个最小值
 */
public class _414_第三大的数 {
    public int thirdMax(int[] nums) {
//    	排序小到大
    	Arrays.sort(nums);
    	int len=nums.length-1;
//    	定义最小值
    	int min=nums[len];
//    	统计最小值交换次数
    	int j=0;
//    	for循环从后往前遍历
    	for(int i=len-1;i>=0;i--) {
//    		如果当前数比最小值小，那么就++
    		if (nums[i]<min) {
				j++;
				min=nums[i];
//				如果统计j到了第三次就直接返回
				if (j==2) {
	    			return nums[i];
				}
			}
    	}
//    	如果没有到第三次就返回最大值
    	return nums[len];
    }
}

转载说明：跟我说明，务必注明来源，附带本人博客连接。