Python实现查找最小的k个数
时间: 2023-06-06 22:05:47 浏览: 41
可以使用heapq模块的nlargest()函数实现查找最小的k个数,代码如下:
```python
import heapq
def findKSmallest(nums, k):
return heapq.nsmallest(k, nums)
nums = [3, 7, 1, 2, 8, 4, 5, 9, 6]
k = 4
print(findKSmallest(nums, k)) # [1, 2, 3, 4]
```
相关问题
两个玻璃球测几层能摔碎python实现
为了回答这个问题,我们首先需要了解一下玻璃球的性质和限制条件。假设这两个玻璃球是同样的大小和质量,并且它们并不会因为摔落而变形或损坏。现在我们可以利用一种二分查找的方法来找到答案。
首先,我们将这个问题转化为一个函数:给定一个楼层数n,判断两个玻璃球摔碎的最小楼层数为多少。假设这个函数为drop(n)。
我们可以从第一层开始尝试,当我们将玻璃球从第k层丢下时,有两种可能的结果:玻璃球摔碎或者没有摔碎。如果玻璃球摔碎了,我们需要在低于第k层的楼层继续尝试,也就是调用drop(k-1)。如果玻璃球没有摔碎,我们需要在高于第k层的楼层继续尝试,也就是调用drop(n-k)。
因此,可以得出递归关系式:drop(n) = 1 + max(drop(k-1), drop(n-k)),其中k取值为1到n。
下面是用Python实现这个函数的代码:
```python
def drop(n):
# 边界条件
if n == 1:
return 1
if n == 0:
return 0
# 初始化最小楼层数为无穷大
min_floor = float('inf')
# 遍历每一层楼
for k in range(1, n+1):
# 当前楼层为k时,计算摔碎和未摔碎的情况下所需要的最小楼层数
cur_floor = 1 + max(drop(k-1), drop(n-k))
# 更新最小楼层数
min_floor = min(min_floor, cur_floor)
return min_floor
```
通过调用`drop(n)`函数,我们可以得到两个玻璃球测几层能摔碎的最小楼层数。
折半查找求阶乘函数后K个零
折半查找求阶乘函数后K个零的方法如下:
1. 定义一个函数 `count_zeros(n)`,表示求n的阶乘末尾有多少个0。
2. 使用二分法,查找一个最小的正整数x,使得 `count_zeros(x) >= k`。
3. 返回x。
具体实现如下:
```python
def count_zeros(n):
count = 0
while n > 0:
n //= 5
count += n
return count
def find_k_zeros(k):
left, right = 1, 5*k
while left < right:
mid = (left + right) // 2
if count_zeros(mid) >= k:
right = mid
else:
left = mid + 1
return left
```
首先定义了一个 `count_zeros` 函数,用于计算n的阶乘末尾有多少个0。这里使用了一个小技巧,就是每次将n除以5,来计算n中因子5的个数。因为阶乘中因子2的个数远多于因子5的个数,所以只需要计算因子5的个数即可。
然后使用二分法,在区间 [1, 5*k] 中查找一个最小的x,使得 `count_zeros(x) >= k`。如果 `count_zeros(x) >= k`,说明x的阶乘末尾至少有k个0,因此需要继续在左半区间查找。如果 `count_zeros(x) < k`,说明x的阶乘末尾不足k个0,因此需要继续在右半区间查找。
最终返回left即可。