算法-求第三大的数

力扣题目：414. 第三大的数 - 力扣（LeetCode）

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

示例 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) 的解决方案吗？

Java实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public static int thirdMax(int[] nums) {
        int L=nums.length;
        for(int i=0;i<L-1;i++)
        {
            for(int j=0;j<L-1-i;j++)
            {
                int tem=nums[j];
                if(nums[j]>nums[j+1])
                {
                    nums[j]=nums[j+1];
                    nums[j+1]=tem;
                }
            }
        }
        //去重复的数字
        List<Integer> list=new ArrayList<>();
        if(L==1)
        {
            return nums[0];
        }
        while(L-1>0)
        {

            if(nums[L-1]!=nums[L-2])
            {

                list.add(nums[L-1]);
            }
            //不等于的情况，倒数第2，第一
            if(L-1==1&&nums[L-1]!=nums[L-2])
            {
                list.add(nums[L-2]);
            }
            if(L-1==1&&nums[L-1]==nums[L-2])
            {
                list.add(nums[L-2]);
            }
            L--;
        }
//        System.out.println(list);

        if(list.size()<3)
        {
            return list.get(0);
        }else
        {
            return list.get(2);
        }
    }

//    public static void main(String[] args) {
//        int[] a=new int[]{1,-2147483648,-2147483648,2};
//        System.out.println(thirdMax(a));
//    }
}

原文地址：https://blog.csdn.net/silent702366/article/details/145199599

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！