编程知识 cdmana.com

【算法千题案例】️每日LeetCode打卡️——54.第三大的数

请添加图片描述


前言

算法题
  • 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程
  • 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
  • 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧🧐!
  • 今天是力扣算法题持续打卡第54天!
算法题

原题样例:. 第三大的数

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

示例:

输入:[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

C#方法:排序

  • 将数组从大到小排序后,从头开始遍历数组,通过判断相邻元素是否不同,来统计不同元素的个数。

  • 如果能找到三个不同的元素,就返回第三大的元素,否则返回最大的元素。

代码:

public class Solution {
    
    public int ThirdMax(int[] nums) {
    
        Array.Sort(nums);
        Array.Reverse(nums);
        for (int i = 1, diff = 1; i < nums.Length; ++i) {
    
            if (nums[i] != nums[i - 1] && ++diff == 3) {
     // 此时 nums[i] 就是第三大的数
                return nums[i];
            }
        }
        return nums[0];
    }
}

执行结果

通过
执行用时:92 ms,在所有 C# 提交中击败了58.36%用户
内存消耗:37.4 MB,在所有 C# 提交中击败了8.56%的用户

C#方法二:有序集合

  • 我们可以遍历数组,同时用一个有序集合来维护数组中前三大的数。

  • 具体做法是每遍历一个数,就将其插入有序集合,若有序集合的大小超过 333,就删除集合中的最小元素。

  • 这样可以保证有序集合的大小至多为 333,且遍历结束后,若有序集合的大小为 333,其最小值就是数组中第三大的数;
    若有序集合的大小不足 333,那么就返回有序集合中的最大值。

代码

public class Solution {
    
    public int ThirdMax(int[] nums) {
    
        SortedSet<int> s = new SortedSet<int>();
        foreach (int num in nums) {
    
            s.Add(num);
            if (s.Count > 3) {
    
                s.Remove(s.Min);
            }
        }
        return s.Count == 3 ? s.Min : s.Max;
    }
}

执行结果

通过
执行用时:92 ms,在所有 C# 提交中击败了58.36%的用户
内存消耗:38.4 MB,在所有 C# 提交中击败了5.21%的用户

复杂度分析

时间复杂度:O( n )
空间复杂度:O( 1 )

Java 方法一:排序

思路解析

  • 将数组从大到小排序后,从头开始遍历数组,通过判断相邻元素是否不同,来统计不同元素的个数。

  • 如果能找到三个不同的元素,就返回第三大的元素,否则返回最大的元素。

代码:

class Solution {
    
    public int thirdMax(int[] nums) {
    
        Arrays.sort(nums);
        reverse(nums);
        for (int i = 1, diff = 1; i < nums.length; ++i) {
    
            if (nums[i] != nums[i - 1] && ++diff == 3) {
     // 此时 nums[i] 就是第三大的数
                return nums[i];
            }
        }
        return nums[0];
    }

    public void reverse(int[] nums) {
    
        int left = 0, right = nums.length - 1;
        while (left < right) {
    
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

执行结果

通过
执行用时:2 ms,在所有 Java  提交中击败了57.82%的用户
内存消耗:38.5 MB,在所有 Java 提交中击败了16.17%的用户

复杂度分析

时间复杂度:O( nlogn )
空间复杂度:O( logn ) 

Java方法二:有序集合

  • 我们可以遍历数组,同时用一个有序集合来维护数组中前三大的数。

  • 具体做法是每遍历一个数,就将其插入有序集合,若有序集合的大小超过 333,就删除集合中的最小元素。

  • 这样可以保证有序集合的大小至多为 333,且遍历结束后,若有序集合的大小为 333,其最小值就是数组中第三大的数;
    若有序集合的大小不足 333,那么就返回有序集合中的最大值。

代码

class Solution {
    
    public int thirdMax(int[] nums) {
    
        TreeSet<Integer> s = new TreeSet<Integer>();
        for (int num : nums) {
    
            s.add(num);
            if (s.size() > 3) {
    
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }
}

执行结果

通过
执行用时:4 ms,在所有 Java  提交中击败了39.49%的用户
内存消耗:38.3 MB,在所有 Java 提交中击败了59.56%的用户

复杂度分析

时间复杂度:O( n )
空间复杂度:O( 1 )

总结

  • 今天是力扣算法题打卡的第五十四天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
    请添加图片描述

版权声明
本文为[呆呆敲代码的小Y]所创,转载请带上原文链接,感谢
https://blog.csdn.net/zhangay1998/article/details/120744523

Scroll to Top