Title address (414. Third largest number)

Leetcode-cn.com/problems/th…

Topic describes

Given a non-empty array, return the third largest number in the array. If not, return the largest number in the array. Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third largest number is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third largest number does not exist, so return the largest number 2. Example 3: Input: [2, 2, 3, 1] Output: 1 Explanation: Note that the third largest number required to return is the third largest number among all the different numbers. 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. 1 <= nums.length <= 104-231 <= nums[I] <= 231-1 Advanced: Can you design a time complexity O(n) solution?Copy the code

Train of thought

With three pointer traversal implementation

code

  • Language support: Python3

Python3 Code:


class Solution:
    def thirdMax(self, nums: List[int]) - >int:
        Use 3 Pointers
        if len(nums) <= 2:
            return max(nums)
        a,b,c= float("-inf"),float("-inf"),float("-inf")
        for i in nums:
            if i > a:
                a,b,c = i,a,b
            elif i>b andi ! =a: b,c = i,belif i>c andi ! =bandi ! =a: c = i# print(a,b,c)
        If C is not yet in turn, return with a
        return c ifc ! =float("-inf") else a

# if __name__ == '__main__':
# nums = [2, 2, 3, 1]
# nums =,1,2 [1]
# result = Solution().thirdMax(nums)
# print(result)




Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)