This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021.
Title description:
414. The third largest number – LeetCode (leetcode-cn.com)
Given a non-empty array, return the third largest number in the array. If not, return the largest number in the array.
The sample a
Input: [3, 2, 1] Output: 1 Explanation: The third largest number is 1.Copy the code
Example 2
Input: [1, 2] Output: 2 Explanation: The third largest number does not exist, so return the largest number 2.Copy the code
Example 3
Input: [2, 2, 3, 1] Output: 1 There are two numbers with a value of 2 in this example, and they are both second. The third largest number of all the different numbers is 1.Copy the code
Tip:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1
Advanced:
Can you design a time complexity O(n)O(n)O(n) O solution?
Thought analysis
The sorting
Sorting is relatively simple, we finish sorting, iterate from the beginning of the time to first reverse the array, and then find the third number is OK, here the main attention to the same element count a line
We have two options
- We reverse it and remove it
- We only need to define a pointer to record
AC code
class Solution {
fun thirdMax(nums: IntArray): Int {
val num = nums.distinct().sorted()
return if (3 <= num.size) {
num[num.size - 3]}else {
num[num.lastIndex]
}
}
}
Copy the code
The Set collection
Since they need to find the third largest number, we only need to maintain a Set of size 3
We iterate over the set of numbers, inserting values into the set, and deleting the smallest element in the set if the ordered set is larger than 3. This ensures that the size of the ordered set is at most 3, and at the end of the traversal, if the size of the ordered set is 3, its minimum value is the third largest number in the array. If the size of the ordered set is less than 3, the maximum value in the ordered set is returned.
AC code
class Solution {
fun thirdMax(nums: IntArray): Int {
val set = TreeSet<Int> ()for (n in nums){
set.add(n)
if(set.size > 3) {
set.remove(set.first())
}
}
if (set.size == 3) {
return set.first()
} else {
return set.last()
}
}
}
Copy the code
conclusion
so easy
reference
The third largest number – the third largest number – LeetCode (leetcode-cn.com)