今天我们一起掌握 leetocode 的 215, 217, 230 题。

1. lc 215 - 数组中的第K个最大元素

  • 题目来源
  • 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
  • 难度：中等

直接想法是排序，然后取倒数第k个值返回，但这不是本题要考察的内容。本题考察手写各种排序，以及理解各种排序的区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        if len(nums)==k: return nums[0] 
        count = 0
        for i in range(len(nums)-1,-1,-1): 
            count += 1 
            if count == k :
                return nums[i]

先贴图，然后手写效率最高的堆排序。

1.1 解题思路 - 堆排序

可以先建立k个元素的小根堆，则堆顶就是最小值。若k之后的元素大于堆顶，则应该插入该堆，从k开始，一直循环遍历完整个数组，则堆顶就是第k大的数。

代码

# 堆排序的思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#可借助python中的heapq模块实现堆的功能, 注意建立的是小根堆
class Solution1:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq as hq
        heap = []
        for i in nums:
            hq.heappush(heap, i)

            if len(heap) > k:
                hq.heappop(heap)
        return heap[0]
      
# 自己实现堆
class Solution2:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        heap = nums[:k]
        # 建立含k个元素的小根堆
        for i in range((k-2)//2, -1, -1):
            self.sift(heap, i, k-1)

        #若k之后的元素大于根节点，则将该元素与根节点替换，然后做一次调整
        for j in range(k,n):
            if nums[j] > heap[0]: #找前k大的数
                heap[0] = nums[j]
                self.sift(heap, 0 , k-1)
        # print(heap)
        return heap[0] #堆顶就是第k大的数了

    # 注意这里要建立小根堆
    def sift(self, alist, low, high):
        # 假设只有根节点需要调整，两棵子树都是堆
        i = low
        j = i *2 +1 #j指向i的左子树
        tmp = alist[i]
        while j <=high:
            if j+1<= high and alist[j] > alist[j+1]: #右子树比较小,则指向右子树
                j = j+1
            if alist[j] < tmp:  # 若子树的值比较小，则根节点换成子树，然后向下看一层
                alist[i] = alist[j]
                i = j
                j = i *2 +1
            else:
                alist[i] = tmp # 子树的值大于根节点，则根节点就放在这一层
                break
        else:
            alist[i] = tmp # j越界跳出循环，则把根节点放在叶子节点

# 作者：xiao-xie-shui-bu-xing
# 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/ge-chong-pai-xu-suan-fa-tu-xie-zong-jie-by-ke-ai-x/

2. lc 217 - 存在重复元素

  • 题目来源
  • 给定一个整数数组，判断是否存在重复元素。 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
  • 难度：简单

2.1 解题思路 - 哈希表

简单题，对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

时间复杂度

  • 时间复杂度： O(n)。
  • 空间复杂度： O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        hashmap = dict()
        for i in range(len(nums)):
            hashmap[nums[i]] = hashmap.get(nums[i],0) + 1
        
            if hashmap[nums[i]] > 1:
                return True
        return False

3. lc 230 - 二叉搜索树中第K小的元素

这里可以用到知识：二叉搜索树的中序遍历是升序；同时，二叉树的前中后序遍历都有两种方法：递归和非递归。

3.1 解题思路 - 递归

构造 BST 的中序遍历序列，第 k-1 个元素就是第 k 小的元素。

3.2 复杂度分析

  • 时间复杂度：O(n)。遍历了整个树。
  • 空间复杂度：O(n)。用了一个数组存储中序序列。

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """ 
        return self.recursion(root)[k-1]

    def recursion(self, root):
        if not root: return []
        else:
            left = self.recursion(root.left) 
            right = self.recursion(root.right)
            return left + [root.val] + right

3.2 解题思路 - 栈 + 迭代

每次将左子树加入到栈中，然后每次pop出后，再查找右子树。

首先，确定是二叉树搜索树。然后，将5，3，2放入栈；无右子树时，pop出节点，k减1；有右子树时，同样操作查阅右子树的左子树，并加入栈。从而，我们发现，对于二叉树搜索树，pop出节点的值是从小到大的。

3.2 复杂度分析

  • 时间复杂度： O(H+k)，其中 H 指的是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为 O(logN+k)。当树是一个不平衡树时：复杂度为 O(N+k)，此时所有的节点都在左子树。

  • 空间复杂度： O(H+k)。当树是一个平衡树时：O(logN+k)。当树是一个非平衡树时：O(N+k)。

3.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """ 
        stack = []
        while True:
            # 走到左子树末尾:将所有左节点放入stack
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

参考

[1] https://www.bilibili.com/video/BV1ha4y1i7dZ?from=search&seid=15243370538903694910