Closed. This question needs to be more focused 。它目前不接受答案。












想改善这个问题吗?更新问题,使其仅通过 editing this post 关注一个问题。

4年前关闭。



Improve this question




我遇到了一个问题,我需要在给定的整数数组中找到可以满足给定总和的对。

我想到的第一个解决方案是检查所有可能的对,大约是 O(n^2) 时间,但面试官要求我提出改进的运行时间,我建议对数组进行排序,然后进行二分搜索但这也是 O(nlogn)。

总的来说,我没有想出 O(n) 解决方案。谷歌搜索我开始知道它可以通过使用 set 的额外内存来实现。

我知道思考算法没有任何固定规则,但我很乐观,认为在思考数组算法时必须有一些启发式或心理模型。我想知道是否有任何通用策略或特定于数组的思维可以帮助我探索更多关于解决方案而不是装死。

最佳答案

一般先天真地想想怎么做。如果在面试中,明确你在做什么,说“好吧,天真的算法将是......”。

然后看看你是否可以看到任何重复的工作或多余的步骤。面试问题往往有点不切实际,是数学特殊案例类型的问题。实际问题更多地归结为使用哈希表或排序数组。排序是 N log N,但它使所有后续搜索 O log N,因此通常值得对数据进行排序。如果数据是动态的,则通过二叉搜索树(C++“set”)对其进行排序。

其次,你能不能“分而治之”或“建立”。 N = 2 的情况是微不足道的吗?在这种情况下,我们可以将 N = 4 分成两个 N = 2 的情况,然后再进行一个积分步骤吗?您可能需要将输入分成两组,低和高,在这种情况下它是“分而治之”,或者您可能需要从随机对开始,然后合并为四,八等,在这种情况下是“建立”。

如果问题是几何问题,你能利用局部相干性吗?如果问题是现实的而不是数学问题,并且您可以利用典型的输入(真正的旅行推销员不会在随机网格上的城市之间旅行,而是通过枢纽和辐条运输系统,快速道路连接主要城市,慢速道路然后分支到客户目的地)?

10-08 00:33
查看更多