Python 数组操作实战：LeetCode 1491 与 912 题，掌握排序与极值剔除 2 类场景

Python 数组操作实战LeetCode 1491 与 912 题掌握排序与极值剔除 2 类场景在数据处理和算法问题中数组操作是最基础也是最重要的技能之一。无论是日常开发还是技术面试高效地处理数组数据都是程序员必备的能力。本文将聚焦两类核心数组操作场景极值处理和全序排列通过 LeetCode 1491 和 912 两道经典题目带你深入理解 Python 中数组操作的精髓。1. 极值处理LeetCode 1491 题解析极值处理是数据分析中常见的需求比如在统计工资时去掉最高和最低的极端值计算更合理的平均值。LeetCode 1491 题正是这类场景的典型代表。1.1 问题描述与基础解法题目要求给定一个唯一整数的工资数组去掉最低和最高工资后计算剩余工资的平均值。最直观的解法是找到数组中的最小值和最大值计算总和后减去这两个极值除以剩余元素数量def average(salary): total sum(salary) min_val min(salary) max_val max(salary) return (total - min_val - max_val) / (len(salary) - 2)这种解法的时间复杂度为 O(n)因为需要遍历数组三次sum、min、max各一次。空间复杂度为 O(1)只使用了常数级别的额外空间。1.2 优化思路与变体当数据量特别大时比如 n 10^6我们可以考虑优化遍历次数def average(salary): min_val max_val salary[0] total 0 for num in salary: total num if num min_val: min_val num elif num max_val: max_val num return (total - min_val - max_val) / (len(salary) - 2)这个版本只需要一次遍历虽然时间复杂度仍然是 O(n)但在大数据量时性能会更好。实际应用场景数据清洗时去除异常值评分系统中去掉最高分和最低分金融分析中过滤极端交易记录2. 全序排列LeetCode 912 题深度解析排序是计算机科学中最基础的算法之一LeetCode 912 题要求我们实现一个数组排序算法且不能使用内置的排序函数。2.1 常见排序算法比较算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(k)稳定2.2 Python 实现归并排序归并排序是解决这类问题的好选择因为它稳定且时间复杂度有保障def sortArray(nums): def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result return merge_sort(nums)2.3 快速排序实现快速排序在实际应用中通常表现更好def sortArray(nums): def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] i low - 1 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[high] arr[high], arr[i 1] return i 1 quick_sort(nums, 0, len(nums) - 1) return nums注意快速排序在最坏情况下如数组已经有序会退化为 O(n^2)可以通过随机选择pivot来优化。3. 综合应用先排序再处理极值在实际开发中我们经常需要组合使用多种数组操作。比如先对数组排序然后再处理极值。3.1 问题场景假设我们需要对数组进行排序去掉前k个最小和后k个最大的元素计算剩余元素的平均值def process_array(nums, k): nums.sort() trimmed nums[k:-k] if k 0 else nums[:] return sum(trimmed) / len(trimmed) if trimmed else 03.2 性能考量不同数据规模下的算法选择数据规模推荐算法原因n ≤ 1000内置sort实现简单常数因子小1000 n ≤ 10^6快速排序平均性能最好n 10^6归并排序稳定O(n log n)保证4. 实战技巧与常见陷阱4.1 Python 数组操作优化技巧列表推导 vs 循环列表推导通常更快# 更优 squared [x**2 for x in nums] # 较慢 squared [] for x in nums: squared.append(x**2)切片操作切片会创建新列表大数据量时注意内存# 创建新列表 part nums[start:end] # 内存更友好 for i in range(start, end): process(nums[i])内置函数优势min/max/sum 都是用C实现的比手动循环快4.2 常见错误与避免方法边界条件处理空数组情况所有元素相同的情况k值大于数组长度的情况浮点数精度问题# 不推荐 average (a b) / 2 # 更好 average a / 2 b / 2算法选择错误小数据量使用复杂算法可能适得其反大数据量使用O(n^2)算法会导致性能问题5. 扩展练习与自我提升为了巩固这些数组操作技巧建议尝试以下变体题目极值处理变体去掉前10%的最大值和最小值根据标准差自动识别并去除异常值排序变体按照绝对值大小排序先按奇偶性再按数值大小排序综合题目# 给定数组先排序然后去掉前后各k个元素再计算剩余元素的平均值和中位数 def process_complex(nums, k): nums.sort() trimmed nums[k:-k] if k 0 else nums[:] avg sum(trimmed) / len(trimmed) mid len(trimmed) // 2 median (trimmed[mid] trimmed[~mid]) / 2 return avg, median在实际项目中数组操作的需求往往更加复杂多变。掌握这些基础模式后可以灵活组合应用解决各种实际问题。