Datawhale编程实践（LeetCode 腾讯精选练习50）Task14

1.数组中的第k个最大元素https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

看到这题只想到排序之后取第k个元素，那就是一个最基本的排序问题了

看了解答之后理解了“快速选择”思想，即在快排的过程中只递归目标方向。

 1 import random
 2 class Solution:
 3     def quickSelect(self, a, l, r, index):
 4         q = self.randomPartition(a, l, r)
 5         if q == index:
 6             return a[q]
 7         else:
 8             return self.quickSelect(a, q+1, r, index) if q < index else self.quickSelect(a, l, q-1, index)
 9     def randomPartition(self, a, l, r):
10         i = random.randint(l, r)
11         a[i], a[r] = a[r], a[i]
12         return self.partition(a, l, r)
13     def partition(self, a, l, r):        
14         x = a[r]
15         i = l - 1
16         for j in range(l, r):
17             if a[j] < x:
18                 i += 1
19                 a[i], a[j] = a[j], a[i]
20         i += 1
21         a[i], a[r] = a[r], a[i]
22         return i
23             
24     def findKthLargest(self, nums, k):
25         return self.quickSelect(nums, 0, len(nums)-1, len(nums)-k)

官方解答提出了第二种思想：堆排序+删除，这个在当时数据结构里有记过，现在都忘了。在这里重新结合代码进行理解记忆感觉很有帮助。不过此方法比第一种快速选择方法时间复杂度要高一些。

 1 class Solution:
 2     def findKthLargest(self, nums: List[int], k: int) -> int:
 3 
 4         def adju_max_heap(nums_list, in_node):  # 从当前内部节点处修正大根堆
 5             """"in_node是内部节点的索引"""
 6             l, r, large_idx= 2*in_node+1, 2*in_node+2, in_node  # 最大值的索引默认为该内部节点
 7 
 8             if l < len(nums_list) and nums_list[large_idx] < nums[l]:  
 9                 # 如果左孩子值大于该内部节点的值，则最大值索引指向左孩子
10                 large_idx = l
11             if r < len(nums_list) and nums_list[large_idx] < nums[r]:
12                 # 如果执行了上一个if语句，此时最大值索引指向左孩子，否则还是指向该内部节点
13                 # 然后最大值索引指向的值和右孩子的值比较
14                 large_idx = r
15 
16             # 上述两个if就是得到(内部节点，左孩子，右孩子)中最大值的索引
17             if large_idx != in_node: # 如果最大值在左孩子和右孩子中，则和内部节点交换
18                 nums_list[large_idx], nums_list[in_node] = nums_list[in_node], nums_list[large_idx]
19                 # 如何内部节点是和左孩子交换，那就递归修正它的左子树，否则递归修正它的右子树
20                 adju_max_heap(nums_list, large_idx)
21 
22         def build_max_heap(nums_list):  # 由列表建立大根堆
23             """"从后往前遍历所有内部节点，其中最后一个内部节点的公式为len(nums_list)//2 - 1"""
24             for in_node in range(len(nums_list)//2 - 1, -1, -1):
25                 adju_max_heap(nums_list, in_node)
26         
27         def find_kth_max(nums_list, k):  # 从列表中找到第k个最大的
28             build_max_heap(nums_list)  # 先建立大根堆
29             for _ in range(k-1):
30                 nums_list[0], nums_list[-1] = nums_list[-1], nums_list[0]  # 堆头和堆尾交换
31                 nums_list.pop()  # 删除堆尾
32                 adju_max_heap(nums_list, 0)  # 从堆头处开始修正大根堆
33             return nums_list[0]
34         return find_kth_max(nums, k)

2.存在重复元素https://leetcode-cn.com/problems/contains-duplicate/

简单题，学到了python的set()方法

1 class Solution:
2     def containsDuplicate(self, nums: List[int]) -> bool:
3         return len(nums) != len(set(nums))

3.二叉搜索树中第k小的元素https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/