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

  1. We reverse it and remove it
  2. 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)