陕西省住房建设厅官方网站,怎样申请免费的网站空间,做动态效果的网站,海南做网站的公司哪家好目录
一、找到K个最接近的元素
1.1 具体思路
1.2 思路展示
1.3 代码实现
1.4 复杂度分析
1.5 运行结果
二、前K个高频元素
2.1 思路一#xff1a;哈希表
2.2 思路二#xff1a;快速选择
2.3 思路三#xff1a;堆
三、柱形图中的最大矩形
3.1 具体思路
3.2 思路…目录
一、找到K个最接近的元素
1.1 具体思路
1.2 思路展示
1.3 代码实现
1.4 复杂度分析
1.5 运行结果
二、前K个高频元素
2.1 思路一哈希表
2.2 思路二快速选择
2.3 思路三堆
三、柱形图中的最大矩形
3.1 具体思路
3.2 思路展示
3.3 代码实现
3.4 复杂度分析
3.5 运行结果
四、接雨水
4.1 具体思想
4.2 代码实现
4.3 复杂度分析
4.4 运行结果
结尾语
人总是无限接近幸福的时候最幸福 一、找到K个最接近的元素
力扣第658题 本题采用二分查找和双指针的方法解决
1.1 具体思路
分两个主要步骤进行
1二分查找找到最接近 x 的数的索引 我们首先定义一个辅助函数 binarySearch用来找到最接近 x 的数的索引。二分查找的过程是如果中间元素比 x 大则索引向左移动如果中间元素比 x 小则索引向右移动如果中间元素等于 x则直接返回索引。
2使用双指针从这个索引开始向两边扩展选择最接近 x 的 k 个数 当找到最接近 x 的数的索引后我们使用双指针从该位置开始向两边扩展以选择最接近 x 的 k 个数。具体过程是根据绝对值大小比较不断向两侧移动指针直到找到 k 个最接近 x 的数。
1.2 思路展示 原始数组: [1, 2, 3, 4, 5, 6, 7, 8, 9]
目标数 x: 5
要选择的最接近 x 的 k 个数: 3
1使用二分查找找到最接近 x 的数的索引即 5 的索引为 4 中间值 [1, 2, 3, 4, 5, 6, 7, 8, 9] ^ | index 4
2 使用双指针从索引 4 开始向两边扩展选择最接近 x 的 3 个数。 - 初始化左指针为索引 4右指针为索引 4 - 进行迭代并根据绝对值大小比较移动指针 - 比较 arr[3] 和 arr[5] 的绝对值大小 abs(4 - 5) abs(6 - 5) True 左指针左移一位 - 比较 arr[2] 和 arr[5] 的绝对值大小 abs(3 - 5) abs(6 - 5) True 左指针左移一位 - 比较 arr[1] 和 arr[5] 的绝对值大小 abs(2 - 5) abs(6 - 5) True 左指针左移一位 - 此时左指针移动到索引 1右指针仍然为索引 4选择的最接近 x 的 3 个数为 [2, 3, 4]
1.3 代码实现
def findClosestElements(arr, k, x):def binarySearch(arr, x):left, right 0, len(arr) - 1while left right:mid (left right) // 2if arr[mid] x:left mid 1else:right midreturn leftleft binarySearch(arr, x)right leftwhile right - left k:if left 0:right 1elif right len(arr):left - 1elif abs(arr[left - 1] - x) abs(arr[right] - x):left - 1else:right 1return arr[left:right]# 测试用例 1
arr1 [1, 2, 3, 4, 5]
k1 4
x1 3
print(findClosestElements(arr1, k1, x1)) # 应输出 [1, 2, 3, 4]# 测试用例 2
arr2 [1, 2, 3, 4, 5]
k2 4
x2 -1
print(findClosestElements(arr2, k2, x2)) # 应输出 [1, 2, 3, 4]# 其他测试用例
arr3 [1, 3, 5, 7, 9]
k3 3
x3 6
print(findClosestElements(arr3, k3, x3)) arr4 [2, 4, 6, 8, 10]
k4 1
x4 7
print(findClosestElements(arr4, k4, x4)) 1.4 复杂度分析
以上代码实现了一个找到最接近 x 的 k 个数的函数。在这个函数中首先使用二分查找找到最接近 x 的数的索引然后使用双指针从该位置开始向两边扩展选择最接近 x 的 k 个数。下面是对该函数的复杂度分析 二分查找部分的时间复杂度为 O(logn)其中 n 是数组 arr 的长度。 在找到最接近 x 的数的索引之后双指针向两边扩展的过程中最坏情况下需要移动 k 步因此时间复杂度为 O(k)。 因此该函数的总时间复杂度为 O(logn k)。 空间复杂度上除了输入参数外算法中没有使用额外的数据结构因此空间复杂度为 O(1)。 综合来看该函数在时间复杂度上表现良好只需要 O(logn k) 的时间复杂度适用于大多数规模的输入。 1.5 运行结果
结果均与预期结果一致 二、前K个高频元素
力扣第347题 2.1 思路一哈希表
1具体思路
此处我尝试使用哈希表来统计每个元素出现的频率并根据频率来找出前 k 高的元素。具体思路如下
遍历数组 nums使用哈希表 freq_map 统计每个元素的出现频率。
构建一个桶 bucket桶的索引表示元素的出现频率桶中存储具有相同频率的元素。
遍历哈希表 freq_map将每个元素放入对应频率的桶中。
从桶的末尾开始遍历取出前 k 个高频元素。 2思路展示
给定nums [1, 1, 1, 2, 2, 3]
k 2 ① 统计频率 freq_map {1: 3, 2: 2, 3: 1} ②构建桶以频率为索引 bucket [ [], # 索引为0的桶为空 [3], # 索引为1的桶中有元素3 [1, 2], # 索引为2的桶中有元素1和2 [] # 索引为3的桶为空 ] ③取出前 k 个高频元素 result [] 从桶的末尾开始遍历 - 桶索引3为空跳过 - 桶索引2中有元素1和2加入result并更新k - 桶索引1中有元素3加入result并更新k 得到 result [1, 2] 3代码实现
def topKFrequent(nums, k):freq_map {}for num in nums:if num in freq_map:freq_map[num] 1else:freq_map[num] 1max_freq max(freq_map.values())bucket [[] for _ in range(max_freq 1)]for num, freq in freq_map.items():bucket[freq].append(num)result []for i in range(max_freq, 0, -1):if k 0 and bucket[i]:result.extend(bucket[i])k - len(bucket[i])if k 0:breakreturn result[:k]# 示例 1
nums1 [1, 1, 1, 2, 2, 3]
k1 2
print(topKFrequent(nums1, k1)) # 输出: [1, 2]# 示例 2
nums2 [1]
k2 1
print(topKFrequent(nums2, k2)) # 输出: [1]
4复杂度分析 创建频率哈希表遍历整个数组 nums 需要 O(n) 的时间其中 n 是数组的长度。
创建桶和将数字放入桶中同样需要 O(n) 的时间。
构建结果列表对于最坏情况下的循环次数是频率的最大值即 max_freq所以需要 O(max_freq) 的时间。
返回结果列表的前 k 个元素这一步最多需要 O(k) 的时间。
因此总体时间复杂度为 O(n max_freq k)其中 n 是数组的长度max_freq 表示数组中元素的最大频率。在最坏情况下max_freq 会达到 n此时时间复杂度为 O(n)。 空间复杂度主要取决于频率哈希表和桶的使用因此为 O(n max_freq)。 2.2 思路二快速选择
1具体思路
首先我们需要实现一个快速选择算法的辅助函数 partition()用于划分数组。 在 partition() 函数中我们选择一个枢纽元素pivot并将数组划分为两部分小于等于枢纽元素的元素放在左边大于枢纽元素的元素放在右边。同时记录枢纽元素的位置。 如果枢纽元素的位置恰好为 k-1那么枢纽元素就是第 k 高的元素返回它。 如果枢纽元素的位置小于 k-1说明第 k 高的元素在右边的子数组中我们递归地在右边子数组中查找第 k-1 - pivot_index 高的元素。 如果枢纽元素的位置大于 k-1说明第 k 高的元素在左边的子数组中我们递归地在左边子数组中查找第 k 高的元素。
2代码实现
import randomdef topKFrequent(nums, k):freq_map {}for num in nums:if num in freq_map:freq_map[num] 1else:freq_map[num] 1unique_nums list(freq_map.keys())def partition(left, right, pivot_index):pivot_frequency freq_map[unique_nums[pivot_index]]# 1. Move pivot to the endunique_nums[pivot_index], unique_nums[right] unique_nums[right], unique_nums[pivot_index]# 2. Move all elements with frequency greater than the pivots frequency to the leftstore_index leftfor i in range(left, right):if freq_map[unique_nums[i]] pivot_frequency:unique_nums[store_index], unique_nums[i] unique_nums[i], unique_nums[store_index]store_index 1# 3. Move pivot to its final placeunique_nums[right], unique_nums[store_index] unique_nums[store_index], unique_nums[right]return store_indexdef quickselect(left, right, k_smallest):if left right:returnpivot_index random.randint(left, right)pivot_index partition(left, right, pivot_index)if k_smallest pivot_index:returnelif k_smallest pivot_index:quickselect(left, pivot_index - 1, k_smallest)else:quickselect(pivot_index 1, right, k_smallest)n len(unique_nums)quickselect(0, n - 1, n - k)return unique_nums[n - k:]# 示例 1
nums1 [1, 1, 1, 2, 2, 3]
k1 2
print(topKFrequent(nums1, k1)) # 输出: [1, 2]# 示例 2
nums2 [1]
k2 1
print(topKFrequent(nums2, k2)) # 输出: [1]
3复杂度分析
时间复杂度 构建 freq_map 字典的过程需要遍历整个 nums 列表时间复杂度为 O(n)其中 n 是列表的长度。
在 quickselect() 中平均情况下每次递归可以将列表划分为大约一半的大小因此递归的时间复杂度为 O(logn)。
在最坏情况下每次递归只能将列表划分为一个元素的大小因此最坏情况下递归的时间复杂度为 O(n)。
综上所述代码的总体时间复杂度为 O(n klogn)。
空间复杂度 除了输入和输出之外额外使用了一个字典 freq_map 和一个列表 unique_nums 来存储数字及其频率。它们的空间复杂度为 O(n)。
递归过程中不需要额外的空间。因此代码的总体空间复杂度为 O(n)。 2.3 思路三堆
1具体思路
当解决频率前 k 高的元素问题时堆 (Heap) 是一个非常高效的数据结构。
我打算使用最小堆来解决这类问题。
具体过程如下 遍历数组 nums 并使用哈希表记录每个元素的出现频率。
创建一个最小堆遍历哈希表将元素和其频率加入堆中。当堆的大小超过 k 时移除堆顶元素频率最小的元素。
最终堆中剩下的元素即为出现频率前 k 高的元素。 2思路展示 ① 遍历数组并记录每个元素的频率 ②创建最小堆并加入元素频率 ③控制堆大小不超过 k移除堆顶元素 ④堆中剩下的元素即为频率前 k 高的元素 在这个示意图中首先遍历数组并记录每个元素的频率得到哈希表。接下来我们创建一个最小堆并将元素和其频率加入堆中。当堆的大小超过 k 时我们移除堆顶元素频率最小的元素。最终堆中剩下的元素即为出现频率前 k 高的元素。 3代码实现
import heapq
from collections import Counterdef topKFrequent(nums, k):# 使用 Counter 来计算每个元素的频率counts Counter(nums)# 创建一个最小堆heap []for num, count in counts.items():heapq.heappush(heap, (count, num))if len(heap) k:heapq.heappop(heap) # 弹出堆顶的最小频率元素# 堆中剩下的元素即为出现频率前 k 高的元素result [x[1] for x in heap]return result 4运行结果
三种思路一致。
两个示例输入如下
输入: nums [1,1,1,2,2,3], k 2
输入: nums [1], k 1 三、柱形图中的最大矩形
力扣第84题 本题采用单调栈的思想
3.1 具体思路
首先创建一个空栈和一个变量 max_area用于记录最大面积。
遍历柱子的高度数组并依次处理每个柱子。
如果栈为空或当前柱子的高度大于等于栈顶柱子的高度则将当前柱子的索引入栈。
如果当前柱子的高度小于栈顶柱子的高度则说明栈顶柱子的右边界确定了可以计算以栈顶柱子为高的矩形的面积。
弹出栈顶柱子并获取其高度 h 和左边界 left。
计算以栈顶柱子为高的矩形的面积为 area h * (current_index - left - 1)。
更新 max_area 的值为 max(max_area, area)。
重复上述步骤直到栈为空或当前柱子的高度大于栈顶柱子的高度。
遍历结束后如果栈中还有剩余的柱子则按照上述步骤计算以这些柱子为高的矩形的面积并更新max_area 的值。
返回 max_area 作为结果。
3.2 思路展示
给定
柱子高度数组: [2, 1, 5, 6, 2, 3] 给定了一个柱子高度数组为 [2, 1, 5, 6, 2, 3]。
按照思路进行
创建一个空栈和变量 max_area。
遍历柱子高度数组
第一个柱子高度为 2将其索引 0 入栈。
第二个柱子高度为 1小于栈顶柱子的高度 2因此可以确定栈顶柱子的右边界。弹出栈顶柱子计算面积为 2 * (当前索引 1 - 左边界 0 - 1) 2。更新 max_area 的值为 2。
第三个柱子高度为 5大于栈顶柱子的高度 1将其索引 2 入栈。
第四个柱子高度为 6大于栈顶柱子的高度 5将其索引 3 入栈。
第五个柱子高度为 2小于栈顶柱子的高度 6可以确定栈顶柱子的右边界。弹出栈顶柱子计算面积为 6 * (当前索引 4 - 左边界 2 - 1) 6。更新 max_area 的值为 6。
第六个柱子高度为 3小于栈顶柱子的高度 2可以确定栈顶柱子的右边界。弹出栈顶柱子计算面积为 2 * (当前索引 5 - 左边界 4 - 1) 2。更新 max_area 的值为 6。
遍历结束后栈中还剩下两个柱子的索引分别是 2 和 3。按照上述步骤分别计算以这些柱子为高的矩形的面积。
第一个柱子索引为 2计算面积为 5 * (当前索引 6 - 左边界 0 - 1) 10。更新 max_area 的值为 10。
第二个柱子索引为 3计算面积为 6 * (当前索引 6 - 左边界 0 - 1) 12。更新 max_area 的值为 12。
返回 max_area 的值 12 作为最大矩形面积的结果。
3.3 代码实现
def largestRectangleArea(heights):stack [] # 单调栈max_area 0 # 最大面积# 遍历柱子的高度数组for i in range(len(heights)):while stack and heights[i] heights[stack[-1]]:# 弹出栈顶柱子并计算面积h heights[stack.pop()]left stack[-1] if stack else -1 # 左边界栈顶柱子的右边柱子area h * (i - left - 1)max_area max(max_area, area)stack.append(i) # 将当前柱子索引入栈# 处理剩余的柱子while stack:h heights[stack.pop()]left stack[-1] if stack else -1area h * (len(heights) - left - 1)max_area max(max_area, area)return max_area# 示例测试
heights [2, 1, 5, 6, 2, 3]
result largestRectangleArea(heights)
print(最大矩形面积为:, result)heights [2, 4]
result largestRectangleArea(heights)
print(最大矩形面积为:, result)
3.4 复杂度分析
时间复杂度分析: 在代码中我们使用了一个循环来遍历柱子的高度数组这部分的时间复杂度为 O(n)其中 n 是柱子的个数。
在遍历过程中对于每根柱子我们进行了一些入栈和出栈操作这些操作的时间复杂度可以视作 O(1) 的常数级操作。
因此整体上该算法的时间复杂度为 O(n)。
空间复杂度分析: 我们使用了一个栈来存储柱子的索引因此空间复杂度取决于栈的大小。
最坏情况下所有的柱子会依次入栈并弹出此时栈的大小将达到柱子的个数因此空间复杂度为 O(n)。
综上所述该算法的时间复杂度为 O(n)空间复杂度为 O(n)。这意味着该算法在处理较大规模的柱状图时也能够保持较好的效率。
3.5 运行结果
以下是两个示例及预期输出 四、接雨水
力扣第42题
本题依旧采用单调栈的思想解决
4.1 具体思想
初始化一个栈 stack 和变量 water用来存储柱子的索引和计算雨水的总量。
遍历柱子的高度数组 height
如果栈为空或者当前柱子的高度小于等于栈顶柱子的高度则将当前柱子的索引入栈。
如果当前柱子的高度大于栈顶柱子的高度说明有可能可以接到雨水。
弹出栈顶柱子的索引并记为 cur。
如果栈为空则跳过后续操作。
计算当前能接到的雨水量水平宽度为 i - stack[-1] - 1垂直高度为 min(height[i], height[stack[-1]]) - height[cur]。 将水平宽度乘以垂直高度得到雨水量并累加到 water 中。
遍历结束后返回 water 的值即为能接到的雨水总量。 4.2 代码实现
# 定义 trap 函数
def trap(height):stack []water 0for i in range(len(height)):while stack and height[i] height[stack[-1]]:cur stack.pop()if not stack:breakwidth i - stack[-1] - 1h min(height[i], height[stack[-1]]) - height[cur]water width * hstack.append(i)return water# 示例 1的测试
height1 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
result1 trap(height1)
print(示例 1的测试结果, result1)# 示例 2的测试
height2 [4, 2, 0, 3, 2, 5]
result2 trap(height2)
print(示例 2的测试结果, result2) 4.3 复杂度分析
代码中的 trap 函数使用了单调栈的思想其时间复杂度为 O(n)其中 n 为输入列表 height 的长度。下面是对该算法的复杂度分析 时间复杂度遍历一次输入列表 height 需要 O(n) 的时间而在每个索引上最多进行了两次出栈操作和一次入栈操作。因此总的时间复杂度为 O(n)。 空间复杂度额外使用了一个栈来存储柱子的索引当柱子高度单调递减时栈可能会达到最大长度为 n。因此空间复杂度也为 O(n)。 综上所述这段代码的时间复杂度为 O(n)空间复杂度为 O(n)。这意味着在处理长度为 n 的输入列表时算法的执行时间和所需的内存空间都与 n 成线性关系。 4.4 运行结果 示例 2
输入height [4,2,0,3,2,5]
输出9 输出均与预期结果一致 结尾语
人总是无限接近幸福的时候最幸福
“ , .”
天天开心
2024-2-1
