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

2024-01-08 10:23:32

在这里插入图片描述


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


在这里插入图片描述

文章来源:https://blog.csdn.net/YZL40514131/article/details/135435721
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。