关于《编程面试要素》13.12题薪资上限算法O(1)空间的疑问

先明确问题背景与题目细节：

ABC公司需将薪资总额削减至指定目标值，CEO计划通过设定去年薪资的上限实现：去年薪资超过上限的员工今年按上限发放，未超过的薪资不变。例如，5名员工去年薪资为$90、$30、$100、$40、$20，目标薪资总额为$210时，合适的上限是$60，因60+30+60+40+20=210。需设计算法，根据现有薪资和目标总额计算薪资上限。

课本给出的解决方案代码如下：

def find_salary_cap(target_payroll, current_salaries):
    current_salaries.sort()
    unadjusted_salary_sum = 0.0
    for i, current_salary in enumerate(current_salaries):
        adjusted_people = len(current_salaries) - i
        adjusted_salary_sum = current_salary * adjusted_people
        if unadjusted_salary_sum + adjusted_salary_sum >= target_payroll:
            return (target_payroll - unadjusted_salary_sum) / adjusted_people
        unadjusted_salary_sum += current_salary
    # No solution, since target_payroll > existing payroll.
    return -1.0

你的疑问解答： #

1. 课本的解决方案是否已经使用O(1)空间？

答案是不一定，核心取决于排序步骤的空间复杂度：

• 代码中调用的current_salaries.sort()是Python列表的原地排序方法（基于Timsort实现）。但Timsort在排序过程中需要额外的辅助空间，最坏情况下空间复杂度为O(n)（n为薪资数组长度），所以使用默认排序的话，整个算法的额外空间复杂度达不到O(1)。
• 这里要注意：「原地排序」不等于「O(1)空间排序」，原地排序仅指不额外开辟与输入同规模的数组存储结果，但仍可能需要一定量的辅助空间。

2. 能否仅用O(1)空间解决该问题？

当然可以，只需要把排序步骤替换为真正的O(1)空间原地排序算法即可：

• 最优选择是堆排序：堆排序是原地排序算法，额外空间复杂度为O(1)（仅需常数级临时变量），时间复杂度为O(n log n)，和Timsort处于同一效率量级。
• 替换排序步骤后，后续的遍历逻辑和原代码完全一致，整个算法的额外空间就能做到O(1)。
• 如果不介意时间效率降低（比如面试场景允许），也可以选择冒泡排序、插入排序这类O(1)空间但O(n²)时间的排序算法，但堆排序显然是更优方案。

另外补充：如果题目允许修改输入数组（大多数编程面试场景默认允许，除非明确禁止），用堆排序替换默认的Timsort就能满足O(1)空间要求；如果不允许修改输入，还可以通过迭代实现快速选择来找到分割点，同样能做到O(1)空间，但实现复杂度会更高。

内容的提问来源于stack exchange，提问作者nataman