数组中唯一可整除两数的高效查找算法探讨（Advent of Code）

嘿，这个问题我刚好在做Advent of Code的时候碰到过！确实有比暴力嵌套循环更高效的解法，咱们来聊聊具体思路：

核心前提 #

首先得明确题目里的关键条件：数组中唯一存在一对满足“一个数能被另一个数整除”的元素。这个唯一性是我们优化的重要基础——不用考虑多对匹配的情况，找到第一对符合条件的就能直接返回结果。

优化思路：排序+倍数查找 #

暴力法的问题在于每个元素都要和所有其他元素比对，时间复杂度O(n²)。我们可以先对数组排序，把时间复杂度的瓶颈降到O(n log n)，再通过有序数组的特性快速定位匹配对：

1. 排序数组：将数组从小到大排序，比如输入[5,9,2,8]排序后得到[2,5,8,9]。排序的时间复杂度是O(n log n)，这是整个流程的主要时间开销。
2. 遍历查找倍数：遍历排序后的每个元素x，在数组中查找比x大的、且是x整数倍的元素。因为数组有序，我们可以直接从x的下一个位置开始，按倍数跳跃检查（比如x=2，就找4、8、12...直到超过数组最大值）。由于题目保证唯一一对，找到第一个匹配的元素就可以停止。

举个具体例子：

• 输入[9,4,7,3]排序后是[3,4,7,9]
• 遍历到3时，检查它的倍数：6（数组中没有）、9（存在），直接得到9/3=3，结束查找。

时间复杂度分析 #

排序的时间是O(n log n)，后续的遍历查找环节，每个元素x最多需要检查log(max_num)次倍数（其中max_num是数组中的最大值），整体时间复杂度是O(n log max_num)。因为log max_num远小于n（当n较大时），所以整个解法的时间复杂度可以认为是O(n log n)，比暴力法的O(n²)高效得多。

额外说明 #

这个解法默认数组中的元素都是正整数（题目示例也符合这个前提）。如果存在0的情况，需要额外处理，但题目里的示例和描述都没涉及，所以暂时不用考虑。

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