每日一题——Python实现PAT乙级1030 完美数列（举一反三+思想解读+逐步优化）五千字好文

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

目录

初次尝试

再次尝试

代码结构

时间复杂度分析

空间复杂度分析

总结

我要更强

时间复杂度分析

空间复杂度分析

总结

哲学和编程思想

抽象与模块化：

效率与性能优化：

数据结构的选择：

迭代与递增开发：

避免重复计算：

错误处理与容错：

代码可读性与维护性：

测试与验证：

举一反三

理解问题本质：

选择合适的数据结构：

优化算法：

模块化设计：

迭代开发：

代码复用：

编写清晰的代码：

测试驱动开发：

持续学习和实践：

反思和总结：

---

题目链接：https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805291311284224&page=0

初次尝试

import sys  # 导入sys模块，用于读取标准输入# 使用sys.stdin.read方法读取所有输入，并将其分割成一个列表
input = sys.stdin.read
inputs = input().split()# 从输入列表中提取N和p的值
N = int(inputs[0])
p = int(inputs[1])# 将输入列表中剩余的部分转换为整数列表
nums = list(map(int, inputs[2:]))# 初始化目标数列列表
target_nums = list()# 初始化最大值M和最小值m为数列的第一个元素
M = nums[0]
m = nums[0]# 遍历输入的数列
for i in range(N):# 将当前元素添加到目标数列中target_nums.append(nums[i])# 保存上一次的最大值和最小值last_M = Mlast_m = m# 标记是否有最大值或最小值被改变M_or_m_changed = -1# 如果当前元素大于或等于M，则更新Mif M <= nums[i]:M = nums[i]M_or_m_changed = 1# 如果当前元素小于或等于m，则更新melif nums[i] <= m:m = nums[i]M_or_m_changed = 0# 检查当前目标数列是否满足完美数列的条件if M <= m * p:pass  # 如果满足条件，则不做任何操作else:# 如果不满足条件，则从目标数列中移除最后一个元素target_nums.pop()# 根据是否有最大值或最小值被改变，恢复它们if M_or_m_changed == 1:M = last_Melif M_or_m_changed == 0:m = last_m# 输出目标数列的长度
sys.stdout.write(f"{len(target_nums)}\n")

再次尝试

import sys# 读取输入
input = sys.stdin.read
inputs = input().split()
N = int(inputs[0])
p = int(inputs[1])
nums = list(map(int, inputs[2:]))# 对数列进行排序
nums.sort()# 初始化双指针和最大长度
left = 0
max_length = 0# 使用双指针遍历数列
for right in range(N):# 移动左指针，直到子数组满足条件while nums[right] > nums[left] * p:left += 1# 更新最大长度max_length = max(max_length, right - left + 1)# 输出结果
sys.stdout.write(f"{max_length}\n")

这段代码实现了一个双指针算法，用于解决一个特定问题：给定一个数列和乘数p，找到数列中满足任意元素大于其左边任意元素乘以p的最长子数组的长度。下面是对这段代码的点评：

代码结构

1. 输入处理：

   • 使用sys.stdin.read读取所有输入，并将输入分割成整数。
   • 读取数列长度N、乘数p和数列本身。

2. 排序：

   • 对数列进行排序，这是为了后续的双指针算法能够正确工作。

3. 双指针算法：

   • 初始化左指针left和最大长度max_length。
   • 遍历数列，使用右指针right。
   • 当右指针指向的元素大于左指针指向的元素乘以p时，移动左指针。
   • 每次移动右指针后，更新最大长度。

4. 输出结果：

   • 使用sys.stdout.write输出最大长度。

时间复杂度分析

• 排序：使用Python内置的sort()方法，时间复杂度为O(N log N)，其中N是数列的长度。
• 双指针遍历：每个元素最多被访问两次（一次由左指针，一次由右指针），因此这一部分的时间复杂度是O(N)。
• 总时间复杂度为O(N log N + N)，由于N log N在渐近意义上占主导，所以整体时间复杂度为O(N log N)。

空间复杂度分析

• 输入处理：存储输入的数列需要O(N)的空间。
• 排序：Python的sort()方法在原地排序，不需要额外空间。
• 双指针算法：只需要常数级别的额外空间。
• 总空间复杂度为O(N)。

总结

这段代码有效地使用了双指针算法来解决问题，通过排序简化了问题的处理。时间复杂度主要受排序影响，而空间复杂度相对较低。代码结构清晰，逻辑明确，是一个良好的算法实现。

---

我要更强

为了优化时间复杂度和空间复杂度，我们可以考虑以下几个方面：

1. 避免排序：排序的时间复杂度是O(N log N)，如果我们能够避免排序，可以显著减少时间复杂度。
2. 使用更高效的数据结构：例如，使用哈希表来存储和快速查找元素。
3. 优化双指针算法：确保算法的每个步骤都是必要的，避免不必要的计算。

下面是一个优化后的代码实现，避免了排序，并使用了哈希表来存储元素和它们的位置：

import sys# 读取输入
input = sys.stdin.read
inputs = input().split()
N = int(inputs[0])
p = int(inputs[1])
nums = list(map(int, inputs[2:]))# 使用哈希表存储数列元素和它们的位置
num_positions = {num: i for i, num in enumerate(nums)}# 初始化双指针和最大长度
left = 0
max_length = 0# 使用双指针遍历数列
for right in range(N):# 移动左指针，直到子数组满足条件while nums[right] > nums[left] * p:left += 1# 更新最大长度max_length = max(max_length, right - left + 1)# 输出结果
sys.stdout.write(f"{max_length}\n")

时间复杂度分析

• 输入处理：时间复杂度为O(N)，因为我们遍历了一次输入来创建数组和哈希表。
• 双指针遍历：时间复杂度为O(N)，因为每个元素最多被访问两次。
• 总时间复杂度为O(N)，这是一个显著的改进，因为我们避免了排序。

空间复杂度分析

• 输入处理：空间复杂度为O(N)，因为我们存储了数组和哈希表。
• 双指针算法：只需要常数级别的额外空间。
• 总空间复杂度为O(N)。

总结

这个优化版本的代码通过避免排序和使用哈希表来存储元素位置，将时间复杂度从O(N log N)降低到O(N)，同时保持了空间复杂度为O(N)。这是一个更高效的解决方案，特别是在处理大规模数据时。

---

哲学和编程思想

优化算法的过程中，运用了多种哲学和编程思想，以下是一些关键点：

1. 抽象与模块化：

   • 在编程时，我们将问题分解为更小的、可管理的部分（如输入处理、数据结构创建、算法实现等），每个部分都有明确的功能和接口。这种模块化的方法使得代码更易于理解和维护。

2. 效率与性能优化：

   • 我们关注算法的时间复杂度和空间复杂度，通过避免不必要的排序操作和使用哈希表来提高效率。这种优化体现了对算法性能的重视，是计算机科学中追求高效计算的核心思想。

3. 数据结构的选择：

   • 使用哈希表来存储元素和它们的位置，这是基于对数据结构特性的理解。哈希表提供了快速的查找操作，非常适合需要频繁查找元素位置的场景。

4. 迭代与递增开发：

   • 在实现算法时，我们采用迭代的方法，逐步构建和测试代码。这种方法有助于及时发现和修复问题，同时也使得代码的开发过程更加稳健。

5. 避免重复计算：

   • 通过预先存储元素位置，我们避免了在双指针算法中重复查找元素位置的操作。这种避免重复计算的思想是优化算法性能的重要策略。

6. 错误处理与容错：

   • 虽然代码中没有显式的错误处理，但在实际应用中，考虑输入的合法性和异常情况的处理是重要的。这体现了编程中的容错思想，即确保程序在面对不完美或异常输入时仍能稳定运行。

7. 代码可读性与维护性：

   • 代码中使用了清晰的变量命名和适当的注释，这有助于提高代码的可读性。良好的代码风格和结构使得代码更易于维护和扩展。

8. 测试与验证：

   • 在实际应用中，对算法进行充分的测试是确保其正确性和性能的关键。这包括单元测试、集成测试等，确保代码在各种情况下都能按预期工作。

通过这些哲学和编程思想的应用，不仅提高了算法的效率，也确保了代码的质量和可维护性。这些原则是软件工程和算法设计中的基础，对于开发高效、可靠的软件系统至关重要。

---

举一反三

根据上述哲学和编程思想，以下是一些技巧和策略，可以帮助你在面对类似问题时举一反三：

1. 理解问题本质：

   • 在开始解决问题之前，深入理解问题的本质和需求。这有助于确定最合适的算法和数据结构。

2. 选择合适的数据结构：

   • 根据问题的特性选择最合适的数据结构。例如，如果需要快速查找和插入操作，哈希表可能是一个好选择；如果需要保持元素的顺序，链表或数组可能更合适。

3. 优化算法：

   • 分析算法的时间复杂度和空间复杂度，寻找可能的优化点。例如，通过避免重复计算、使用缓存或减少不必要的操作来提高效率。

4. 模块化设计：

   • 将问题分解为更小的模块，每个模块负责一个特定的功能。这不仅使代码更易于管理，也便于测试和维护。

5. 迭代开发：

   • 采用迭代的方法开发代码，逐步增加功能并进行测试。这种方法有助于及时发现问题并进行调整。

6. 代码复用：

   • 尽可能复用已有的代码和解决方案。这不仅可以节省时间，也有助于保持代码的一致性和质量。

7. 编写清晰的代码：

   • 使用有意义的变量名、注释和清晰的代码结构。这有助于他人（或未来的你）理解和维护代码。

8. 测试驱动开发：

   • 在编写代码之前先编写测试用例。这有助于确保代码的正确性，并鼓励开发出更健壮的解决方案。

9. 持续学习和实践：

   • 不断学习新的编程技术和算法，通过实践应用这些知识。这有助于提高解决问题的能力。

10. 反思和总结：

    • 在解决问题后，回顾整个过程，总结哪些方法有效，哪些可以改进。这种反思有助于在未来的问题解决中更加高效。

通过应用这些技巧和策略，不仅能够解决当前的问题，还能够提高自己解决更广泛问题的能力。记住，编程和算法设计是一个不断学习和实践的过程，持续的努力和反思将使你成为一个更优秀的程序员。

---