215、数组中的第k个最大元素
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
if len(nums) == 1: return nums[0]
mid = int(len(nums) // 2)
left, right, mids = [], [], []
for i in range(len(nums)):
if nums[i] > nums[mid]:
left.append(nums[i])
elif nums[i] < nums[mid]:
right.append(nums[i])
else:
mids.append(nums[i])
if len(left) >= k:
return self.findKthLargest(left, k)
elif len(mids) >= k - len(left):
return nums[mid]
else:
return self.findKthLargest(right, k - len(left) - len(mids))
217、存在重复元素
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)
230、二叉搜索树中第K小的元素
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
def gen(r):
if r is not None:
yield from gen(r.left)
yield r.val
yield from gen(r.right)
it = gen(root)
for _ in range(k):
ans = next(it)
return ans
