leetcode | 414.第三大的数

414.第三大的数

题目描述

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

• 示例 1：
  输入：[3, 2, 1]
  输出：1
  解释：第三大的数是 1 。

• 示例 2：
  输入：[1, 2]
  输出：2
  解释：第三大的数不存在, 所以返回最大的数 2 。

• 示例 3：
  输入：[2, 2, 3, 1]
  输出：1
  解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
  此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

题目链接

思路

1. 排序
   将nums数组排序后，从数组末尾返回第三大的数。
2. 有序集合
   遍历数组，同时用一个有序集合来维护数组中前三大的数。具体做法是每遍历一个数，就将其插入有序集合，若有序集合的大小超过 333，就删除集合中的最小元素。这样可以保证有序集合的大小至多为 333，且遍历结束后，若有序集合的大小为 333，其最小值就是数组中第三大的数；若有序集合的大小不足 333，那么就返回有序集合中的最大值。
3. 一次遍历
   遍历数组，并用三个变量a、b、c来维护数组中的最大值、次大值和第三大值，在遍历过程中更新这三个值即可。

   代码

   class Solution(object):
   	def thirdMax(self, nums):
   		"""
   		排序（自己实现快速排序）
           :type nums: List[int]
           :rtype: int
           """
   		def quick_sort(arr, low, high):
   			if low < high:
   				pivot = partition(arr, low, high)
   				quick_sort(arr, low, pivot - 1)
   				quick_sort(arr, pivot + 1, high)
   		
   		def partition(arr, low, high):
   			pivot_key = arr[low]
   			while low < high:
   				while low < high and arr[high] >= pivot_key:
   					high -= 1
   				arr[low], arr[high] = arr[high], arr[low]
   				while low < high and arr[low] <= pivot_key:
   					low += 1
   				arr[low], arr[high] = arr[high], arr[low]
   			return low
   		
   		quick_sort(nums, 0, len(nums) - 1)
   		
   		
   		diff = 0
   		for i in range(len(nums) - 1, -1, -1):
   			if nums[i] != nums[i - 1]:
   				diff += 1
   				if diff == 2:
   					return nums[i-1]
   					
   		return nums[-1]
   	
   	def thirdMax1(self, nums):
   		"""排序（直接调用排序方法）"""
   		nums.sort(reverse=True)
   		diff = 1
   		for i in range(1, len(nums)):
   			if nums[i] != nums[i-1]:
   				diff += 1
   				if diff == 3:
   					return nums[i]
   		return nums[0]
   	
   	def thirdMax2(self, nums):
   		"""有序集合"""
   		from sortedcontainers import SortedList
   		s = SortedList()
   		for num in nums:
   			if num not in s:
   				s.add(num)
   				if len(s) > 3:
   					s.pop(0)
   		return s[0] if len(s) == 3 else s[-1]
   	
   	def thirdMax3(self, nums):
   		"""一次遍历（用三个变量a,b,c来维护数组中的最大值、次大值和第三大值）"""
   		a, b, c = float('-inf'), float('-inf'), float('-inf')
   		
   		for num in nums:
   			if num > a:
   				a, b, c = num, a, b
   			elif a > num > b:
   				b, c = num, b
   			elif b > num > c:
   				c = num
   		
   		return a if c == float('-inf') else c
   
   if __name__ == "__main__":
   	slt = Solution()
   	# third_max_num = slt.thirdMax([2, 2, 3, 1])
   	# third_max_num = slt.thirdMax1([2, 2, 3, 1])
   	# third_max_num = slt.thirdMax2([2, 2, 3, 1])
   	third_max_num = slt.thirdMax3([2, 2, 3, 1])
   	print(third_max_num)