0x3f 第45天 面向实习的八股背诵第二天 + 堆一题+看见了些不得了的事情总观效应了

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

核心思想：

假设数组升序排列后是[1,2,3,4,5,6]（n=6），第 2 大元素是 5，对应下标6-2=4；

• 不管数组是否有序，「第 K 大元素在升序数组中的下标永远是n-k」
• 随机选 pivot 后，通过双指针划分，能精准确定 pivot 的最终下标 j；
• 划分后：
  • j左边的元素 ≤ pivot，右边的元素 ≥ pivot；
  • nums[j]就是数组中「第 n-j 大」的元素

缩圈直到命中」：迭代找目标下标（二分法的lowerbound）

• 如果j == n-k：直接返回nums[j]（找到答案）；
• 如果j > n-k：目标在左区间[left, j-1]（缩小范围，继续找）；
• 如果j < n-k：目标在右区间[j+1, right]（缩小范围，继续找）。

为什么必须随机一个 pivot，如果固定排序每次的第一个，遇到有序数组时，一次性只能排序一个位置，最终时间复杂度是O（n²），随机就是保证时间复杂度稳定在n

最难的是Partition函数

Partition（划分）的核心作用

随机选一个基准值pivot，把数组划分为「<=pivot」和「>=pivot」两部分；

返回pivot的最终下标j，此时

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def partition(nums,left,right): i = randint(left,right) pivot = nums[i] nums[i],nums[left] = nums[left],nums[i] i,j = left+1,right while True: while i<=j and nums[i]<pivot: i += 1 while i<=j and nums[j]>pivot: j -= 1 if i>=j: break nums[i],nums[j] = nums[j] ,nums[i] i += 1 j -= 1 nums[left],nums[j] = nums[j],nums[left] return j n = len(nums) target = n-k left,right = 0, n-1 while True: i = partition(nums,left,right) if i==target: return nums[i] elif i>target: right = i-1 else: left = i+1

2.面向实习的八股文今天背诵了：

接口和抽象类的区别，反射的概念反射的底层原理反射的使用场景反射的优缺点，java有哪些集合类型，arraylist和linkedlist的区别，hashmap的概念，hashmap的数据结构，hashmap怎么实现扩容，hashmap线程不安全怎么办