一、python实现一亿个无序数找出 Top 100
思路：
使用堆数据结构
1、先创建一个空的堆
2、遍历一亿个无序数，对于每个数，如果堆的大小小于100，我们将该数直接加入堆中；
3、否则，我们将该数与堆顶元素比较，如果大于堆顶元素，将堆顶元素弹出，再将该数加入堆中。
4、最后，我们将堆中的元素按照降序排序，即可得到TOP100.
1亿个数
import heapq
def find_top_100(numbers):
heap=[]
for num in numbers:
if len(heap)<100:
heapq.heappush(heap,num)
else:
if num > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap,num)
return sorted(heap,reverse=True)
# 示例用法
numbers = [1000000000 - i for i in range(100000000)]
top_100 = find_top_100(numbers)
print(top_100)
假设有1亿个数换成——》18个数，取TOP 10
import heapq
def find_top_100(numbers):
heap=[]
for num in numbers:
if len(heap)<10:
heapq.heappush(heap,num)
else:
if num > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap,num)
return sorted(heap,reverse=True)
# 示例用法
numbers = [22,61,8,42,2,6,8,52,4,3,5,17,25,31,21,44,7,12]
top_100 = find_top_100(numbers)
print(top_100) #[61, 52, 44, 42, 31, 25, 22, 21, 17, 12]
1、heapq.heappush详解
a、什么是heapq.heappush
在Python中，heapq模块提供了一些堆队列算法。其中一个功能是使用heappush()方法将元素添加到堆中。
堆是树状结构，其中一个结点的值不大于其父节点的值，也称为最小堆。。这意味着堆顶元素始终是堆中的最小值
b、heapq.heappush的语法
heapq.heappush(heap, item)
这个函数将item添加到heap表示的堆中。heap是由元素组成的列表或类似列表的迭代器。
这个函数会调整heap使得其仍为最小堆。
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)
print("堆队列中的元素为：", end="")
for i in heap:
print(i, end=",")
这段代码将数字3、1、4、2依次添加到heap列表中。
由于在添加元素时进行了调整，最终堆队列中的元素为1、2、4、3。
二、2215. 找出两数组的不同
简单
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：
answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
注意：列表中的整数可以按 任意 顺序返回。
示例 1：
输入：nums1 = [1,2,3], nums2 = [2,4,6]
输出：[[1,3],[4,6]]
解释：
对于 nums1 ，nums1[1] = 2 出现在 nums2 中下标 0 处，然而 nums1[0] = 1 和 nums1[2] = 3 没有出现在 nums2 中。因此，answer[0] = [1,3]。
对于 nums2 ，nums2[0] = 2 出现在 nums1 中下标 1 处，然而 nums2[1] = 4 和 nums2[2] = 6 没有出现在 nums2 中。因此，answer[1] = [4,6]。
示例 2：
输入：nums1 = [1,2,3,3], nums2 = [1,1,2,2]
输出：[[3],[]]
解释：
对于 nums1 ，nums1[2] 和 nums1[3] 没有出现在 nums2 中。由于 nums1[2] == nums1[3] ，二者的值只需要在 answer[0] 中出现一次，故 answer[0] = [3]。
nums2 中的每个整数都在 nums1 中出现，因此，answer[1] = [] 。
重点：集合中差集
1、集合的差集
两个集合的差集包含了第一个集合中存在，但第二个集合中不存在的所有元素。
以下是集合 s1 和 s2：
s1 = {'Python', 'Java', 'C++'}
s2 = {'C#', 'Java', 'C++'}
s1 和 s2 的差集结果只有一个元素：
s = s1 - s2
{'Python'}
因为“Python”属于第一个集合，但不属于第二个集合。
集合的差集不具有可交换性，s2 和 s1 的差集如下：
s = s2 - s1
{'C#'}
在 Python 中，我们可以使用集合的 difference() 方法或者交集操作符（-）返回两个或多个集合的差集。
from collections import Counter
class Solution(object):
def findDifference(self, nums1, nums2):
se1, se2 = set(nums1), set(nums2)
return [list(se1 - se2), list(se2 - se1)]
s=Solution()
nums1 = [1,2,3,3]
nums2 = [1,1,2,2]
print(s.findDifference(nums1, nums2))
三、计算相同字符个数，并按个数排序，返回前 k 个
def func(strs,k):
res=Counter(strs)
res1=sorted(res.items(),key=lambda x:x[1],reverse=True)
res2=list(map(lambda x:x[0],res1))
return res2[:k]
strs="qweqwewt"
print(func(strs,k=2))
四、返回 s2 在 s1 中的位置，要求不能使用 indexOf，并且输入任何字符串都能返回位置，如果没有，返回 0；
def func1(s,s1):
res=s.split(s1)
if len(res)==1:
return 0
return len(res[0])
s='qweqwe'
s1='we1'
print(func1(s,s1))
