python数据结构与算法

ops/2024/9/23 9:24:17/

0.时间复杂度和空间复杂度

快速判断算法时间复杂度算法运行时间

1.确定问题规模n
2.循环减半 logn
3.k层关于n的循环 n^k

空间复杂度:评估算法内存占用大小

使用几个变量 O(1)
使用长度为n的一维列表 O(n)
使用m行n列的二维列表 O(mn)

1.递归

递归三步曲:
1.递归参数和返回值
2.终止条件
3.递归

2.二分查找

内置函数 .index() #输入待查找元素 ,输出元素下标,没找到返回None或-1
二分查找的代码

python">nums 是有序数组
def binary_search(nums, val):left = 0right = len(nums)-1while left <= right:  #值在闭区间【left,right】找mid = (left+right)//2if nums[mid]< val:  #待查找的值在mid右left = mid +1elif nums[mid] > val:  #待查找的值在mid左right = mid -1else:return midreturn -1  #在nums里面找不到val

3.排序介绍

列表排序 内置函数 sort()
常见的排序算法

差生三人组O(n^2)好生三人组O(nlogn) 【运行时间:快排<归并<堆排序】其他排序
冒泡排序快速排序:极端情况,排序效率低希尔排序
选择排序堆排序:在快的排序算法中相对较慢计数排序
插入排序归并排序:需要额外的内存开销基数排序

在这里插入图片描述
稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同

3.1 冒泡排序

基本思想

1.列表每两个相邻的数,如果前面比后面大,则交换位置
2.一趟排序完成,则无序区减少一个数, 有序区增加一个数
【每一趟,都把当前无序区最大的数,放到有序区】

python">def bubble_sort(nums):for i in range(len(nums)-1): # 第 i趟exchange = Falsefor j in range(len(nums)-i-1):if nums[j] > nums[j+1]:nums[j], nums[j+1] = nums[j+1], nums[j]   #如果前> 后,则交换exchange = Trueif  not exchange: #一趟下来,没有发生交换,代表剩下的无序区,已经是有序的return 

3.2 选择排序

基本思路:

一趟排序,记录最小的数,放到第一个位置
再一趟排序,记录无序区最小数,放到第二个位置 …

python">def select_sort(nums):for i in range(len(nums)-1):min_index = ifor j in range(i+1, len(nums)):if nums[j] < nums[min_index]:min_index = jif min_index != i:nums[i],nums[min_index] = nums[min_index], nums[i]

3.3 插入排序

基本思路:从无序区来一个数,就插到有序区数组中排好

python">def insert_sort(nums):for i in range(1, len(nums)):temp = nums[i]  #要排的元素j = i-1    #有序区的最后一位while j >=0 and nums[j]>temp:nums[j+1] = nums[j]j = j-1nums[j+1] = temp 			

3.4 快速排序

基本思路在这里插入图片描述

python">def quick_sort(nums, left, right):if left< right:   #保证至少两个元素mid = partition(data, left, right)  #返回哨兵的位置,在排好的数组里面,哨兵的正确位置quick_sort(data, left, mid-1)quick_sort(data, mid+1, right)def partition(nums, left, right):  #复杂度O(n)temp = nums[left]while left < right:while left < right and nums[right] >= temp:  #从右边找比temp小的值right -= 1nums[left] = nums[right]    #把右边的值写在左边的空位上while left < right and nums[left] <= temp:left += 1   nums[right] = nums[left]   #把左边的值写到右边空位上nums[left] = temp  #把temp归位return left

3.6 归并排序

基本思路
在这里插入图片描述

python">def mergeSort(arr):if(len(arr)<2):return arrmiddle = int(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right:if left[0] <= right[0]:result.append(left.pop(0))else:result.append(right.pop(0))while left:result.append(left.pop(0))while right:result.append(right.pop(0))return result

3.5堆排序

大根堆:一颗完全二叉树,满足任一节点都比其孩子节点大
小根堆: …,…小

在这里插入图片描述
堆排序内置模块

python">import heapqheap.heapify(nums)   #建堆
heap.heappush(heap, item)
heap.heappop(heap)			

topK问题:n个数,找前k大的数

思路:
1.快排 O(nlogn)
2.冒泡排序 O(nk)
3.堆排序:维护一个k大的小根堆,不断吐出小数 O(nlogk)

力扣:215.数组中第K个最大的元素
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

在这里插入图片描述

python">class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:pivot = nums[0]small,equal,big = [],[],[]for i in nums:if i> pivot:big.append(i)elif i < pivot:small.append(i)else:equal.append(i)if len(big) >= k:return self.findKthLargest(big, k)elif len(big)< k and len(big) + len(equal)>=k:return pivotelse:return self.findKthLargest(small,k-len(big)-len(equal))

力扣:347.前K个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。

python">import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:rec = {}for i in nums:rec[i] = rec.get(i,0) + 1stack = []for key, value in rec.items():heapq.heappush(stack, (value, key))if len(stack) > k:heapq.heappop(stack)ans = [0] * k  for i in range(k-1, -1, -1):ans[i] = heapq.heappop(stack)[-1]return ans
3.7希尔排序

在这里插入图片描述

3.8 计数排序
python">def count_sort(nums, max_count = 100):count = [0 for _ in range(max_count+1)]for val in nums:count[val]+=1nums.clear()for index, val in enumerate(count):for i in range(val):nums.append(index)
3.8桶排序

桶排序:表现取决于数据分布

3.9基数排序

在这里插入图片描述


http://www.ppmy.cn/ops/86631.html

相关文章

卷积神经网络(三)---案例分析

上面部分介绍了 PyTorch 中的卷积模块&#xff0c;接下来将会介绍几个卷积神经网络的案例&#xff0c;通过案例入手来介绍卷积神经网络的结构设计。 1. LeNet LeNet 是整个卷积神经网络的开山之作&#xff0c;1998年由 LeCun 提出&#xff0c;它的结构特别简单&#xff0c;我们…

【算法】字典序最小的 01 字符串

字典序最小的 01 字符串 题目描述 小红有一个 01 字符串&#xff0c;她可以进行最多 k 次提作&#xff0c;每次操作可以交换相邻的两个字符&#xff0c;问可以得到的字典序最小的字符串是什么。 输入描述 第一行包含两个整数&#xff0c;n&#xff08;1 < n < 10^5&a…

《数据结构1800题》基础回合总结——第1章 绪论

前言&#xff1a;《数据结构1800》这本书相信大家或多或少都有所耳闻&#xff0c;收录了诸多不同档次学校的考研真题&#xff0c;因为和汤老师的1800撞名所以备受调侃。这1800道题目里面有选择有填空&#xff0c;也有简答和一些编程题&#xff0c;总的来说质量良莠不齐——亦或…

MATLAB基础:函数与函数控制语句

今天我们继续学习Matlab中函数相关知识。 API的查询和调用 help 命令是最基本的查询方法&#xff0c;可查询所有目录、指定目录、命令、函数。 我们直接点击帮助菜单即可查询所需的API函数。 lookfor 关键字用于搜索相关的命令和函数。 如&#xff0c;我们输入lookfor inpu…

MATLAB R2017a 安装与破解 ​编辑

转载自 https://www.cnblogs.com/chaofn/p/8323852.html 第一步&#xff1a; 到我的百度网盘下载MatlAB2017a的原安装程序和破解补丁&#xff1a; 链接&#xff1a;百度网盘 请输入提取码 提取密码&#xff1a; d59m 第二步&#xff1a; 下载的两个iso文件&#xff1a;R2…

DHCP笔记

DHCP---动态主机配置协议 作用&#xff1a;为终端动态提供IP地址&#xff0c;子网掩码&#xff0c;网关&#xff0c;DNS网址等信息 具体流程 报文抓包 在DHCP服务器分配iP地址之间会进行广播发送arp报文&#xff0c;接收IP地址的设备也会发送&#xff0c;防止其他设备已经使用…

《数据结构与算法之美》学习笔记三之链表

前言&#xff1a;先回顾一下本系列上一篇文章的大致内容 二叉树 1、二叉树的分类&#xff1a;满二叉树(所有节点都是满满的)、完全二叉树(只有最后一层不满&#xff0c;且最后一层节点都在左边)、二叉搜索树(有顺序)、平衡二叉树(左右子树高度差不超过1或者一棵空树) 2、二叉树…

“八股文”:程序员的福音还是梦魇?

——一场关于面试题的“代码战争” 在程序员的世界里&#xff0c;“八股文”这个词儿可谓是“如雷贯耳”。不&#xff0c;咱们可不是说古代科举考试中的那种八股文&#xff0c;而是指程序员面试中的那些固定套路的题目。如今&#xff0c;各大中小企业在招聘程序员时&#xff0…