python实现一亿个无序数找出Top100

---

一、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))

---