【笔试强训选择题】Day30.习题（错题）解析

**笔试强训选择题 Day30**

**习题解析**

###1. 题目描述在一个有序的整数集合中，要求找出第 k 大数字。假设集合中的数字都是正整数，并且集合中没有重复数字。

###2. 解决方案#### 方法一：排序法

def findKthLargest(nums, k):
 # 将列表转换为有序列表 nums.sort(reverse=True)
 # 返回第 k 大数字 return nums[k-1]

#### 方法二：堆排序法

import heapqdef findKthLargest(nums, k):
 # 使用小顶堆存储前 k 个最大的数字 min_heap = []
 for num in nums:
 # 将数字插入堆中 heapq.heappush(min_heap, num)
 # 如果堆中有 k+1 个数字，弹出最小的数字 if len(min_heap) > k:
 heapq.heappop(min_heap)
 # 返回堆顶元素（第 k 大数字）
 return min_heap[0]

#### 方法三：快速选择法

def findKthLargest(nums, k):
 #选取一个随机索引 pivot_index = int(len(nums) * random.random())
 # 将列表分成两部分 left = [num for i, num in enumerate(nums) if i < pivot_index]
 middle = [num for i, num in enumerate(nums) if i == pivot_index]
 right = [num for i, num in enumerate(nums) if i > pivot_index]
 # 如果 k 等于中间部分的大小，则返回中间部分的元素 if k == len(left):
 return middle[0]
 # 如果 k 小于中间部分的大小，则递归查找左边的第 k 大数字 elif k < len(left) + len(middle):
 return findKthLargest(left, k)
 # 否则，递归查找右边的第 k - len(left) - len(middle) 大数字 else:
 return findKthLargest(right, k - len(left) - len(middle))

###3. 错题解析#### 错误一：排序法中的错误在排序法中，使用了 `reverse=True` 参数来将列表转换为有序列表。然而，这个参数实际上是用于反向排序，而不是正向排序。如果要实现正向排序，可以简单地移除这个参数。

def findKthLargest(nums, k):
 # 将列表转换为有序列表 nums.sort()
 # 返回第 k 大数字 return nums[k-1]

#### 错误二：堆排序法中的错误在堆排序法中，使用了 `min_heap` 变量来存储前 k 个最大的数字。然而，这个变量实际上是用于存储最小的数字，而不是最大数。如果要实现堆排序法，可以简单地将 `min_heap` 变量改为 `max_heap`。

import heapqdef findKthLargest(nums, k):
 # 使用大顶堆存储前 k 个最大的数字 max_heap = []
 for num in nums:
 # 将数字插入堆中 heapq.heappush(max_heap, -num)
 # 如果堆中有 k+1 个数字，弹出最大数 if len(max_heap) > k:
 heapq.heappop(max_heap)
 # 返回堆顶元素（第 k 大数字）
 return -max_heap[0]

#### 错误三：快速选择法中的错误在快速选择法中，使用了 `random.random()` 函数来选取一个随机索引。然而，这个函数实际上是用于生成一个随机浮点数，而不是整数。如果要实现快速选择法，可以简单地将 `int(len(nums) * random.random())` 改为 `random.randint(0, len(nums))`。

import randomdef findKthLargest(nums, k):
 #选取一个随机索引 pivot_index = random.randint(0, len(nums))
 # 将列表分成两部分 left = [num for i, num in enumerate(nums) if i < pivot_index]
 middle = [num for i, num in enumerate(nums) if i == pivot_index]
 right = [num for i, num in enumerate(nums) if i > pivot_index]
 # 如果 k 等于中间部分的大小，则返回中间部分的元素 if k == len(left):
 return middle[0]
 # 如果 k 小于中间部分的大小，则递归查找左边的第 k 大数字 elif k < len(left) + len(middle):
 return findKthLargest(left, k)
 # 否则，递归查找右边的第 k - len(left) - len(middle) 大数字 else:
 return findKthLargest(right, k - len(left) - len(middle))

###4. 总结在本题中，我们使用了三种不同的方法来解决问题：排序法、堆排序法和快速选择法。每种方法都有其优缺点，需要根据具体情况选择合适的方法。在错误一、二、三中，我们分别对排序法、堆排序法和快速选择法进行了改进，使得它们能够正确地实现所需功能。

###5. 最终答案最终答案是：

* 排序法：`findKthLargest(nums, k) = nums.sort()[k-1]`
* 堆排序法：`findKthLargest(nums, k) = -heapq.heappop([-num for num in nums])[0]`
* 快速选择法：`findKthLargest(nums, k) = findKthLargest([num for i, num in enumerate(nums) if i != pivot_index], k)`