网页设计作业电影介绍网站,苏州比较好的建筑公司,tornado网站开发 教程,网站建设南昌0.时间复杂度和空间复杂度
快速判断算法时间复杂度#xff1a;算法运行时间 1.确定问题规模n 2.循环减半 logn 3.k层关于n的循环 n^k 空间复杂度#xff1a;评估算法内存占用大小 使用几个变量 O#xff08;1#xff09; 使用长度为n的一维列表 O#xff08;n#xff09…0.时间复杂度和空间复杂度
快速判断算法时间复杂度算法运行时间 1.确定问题规模n 2.循环减半 logn 3.k层关于n的循环 n^k 空间复杂度评估算法内存占用大小 使用几个变量 O1 使用长度为n的一维列表 On 使用m行n列的二维列表 Omn 1.递归
递归三步曲 1.递归参数和返回值 2.终止条件 3.递归
2.二分查找
内置函数 .index() #输入待查找元素 输出元素下标没找到返回None或-1 二分查找的代码
nums 是有序数组
def binary_search(nums, val):left 0right len(nums)-1while left right: #值在闭区间【leftright】找mid (leftright)//2if nums[mid] val: #待查找的值在mid右left mid 1elif nums[mid] val: #待查找的值在mid左right mid -1else:return midreturn -1 #在nums里面找不到val3.排序介绍
列表排序 内置函数 sort() 常见的排序算法
差生三人组O(n^2)好生三人组Onlogn 【运行时间快排归并堆排序】其他排序冒泡排序快速排序:极端情况排序效率低希尔排序选择排序堆排序在快的排序算法中相对较慢计数排序插入排序归并排序需要额外的内存开销基数排序 稳定性排序后 2 个相等键值的顺序和排序之前它们的顺序相同
3.1 冒泡排序
基本思想 1.列表每两个相邻的数如果前面比后面大则交换位置 2.一趟排序完成则无序区减少一个数 有序区增加一个数 【每一趟都把当前无序区最大的数放到有序区】 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[j1]:nums[j], nums[j1] nums[j1], nums[j] #如果前 后则交换exchange Trueif not exchange: #一趟下来没有发生交换代表剩下的无序区已经是有序的return 3.2 选择排序
基本思路 一趟排序记录最小的数放到第一个位置 再一趟排序记录无序区最小数放到第二个位置 … def select_sort(nums):for i in range(len(nums)-1):min_index ifor j in range(i1, 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 插入排序
基本思路从无序区来一个数就插到有序区数组中排好
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[j1] nums[j]j j-1nums[j1] temp 3.4 快速排序 基本思路 def quick_sort(nums, left, right):if left right: #保证至少两个元素mid partition(data, left, right) #返回哨兵的位置在排好的数组里面哨兵的正确位置quick_sort(data, left, mid-1)quick_sort(data, mid1, right)def partition(nums, left, right): #复杂度O(ntemp 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 归并排序 基本思路 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堆排序
大根堆一颗完全二叉树满足任一节点都比其孩子节点大 小根堆: ……小 堆排序内置模块 import heapqheap.heapify(nums) #建堆
heap.heappush(heap, item)
heap.heappop(heap) topK问题n个数找前k大的数
思路 1.快排 Onlogn 2.冒泡排序 Onk 3.堆排序维护一个k大的小根堆不断吐出小数 O(nlogk
力扣215.数组中第K个最大的元素 给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。 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 高的元素。
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 ans3.7希尔排序 3.8 计数排序
def count_sort(nums, max_count 100):count [0 for _ in range(max_count1)]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基数排序
