假设您有一个排序的向量{xi}i=1n,其元素均为正数且不包含平局(=此向量中没有两个元素相同)。
我正在寻找检查以下内容的最聪明方法:
对于所有1 <= i != j != k <= n,2xi - xj - xk != 0。
我有一种预感,这可以在O(nlog n)的时间内完成,或者以比朴素更好的方式进行,可能使用类似于this question中开发的策略。
请记住,x的条目都是正数并且已排序,因此x_k+k_j的条目也已排序。
附言:我正在寻找算法/语言不可知的想法。 C++标签主要用于在需要利用某些智能缓存策略时执行此操作。
编辑:
我正在寻找检查以下内容的最聪明方法:
对于所有1 <= i != j != k <= n,2xi - xj - xk != 0。
我有一种预感,这可以在O(nlog n)的时间内完成,或者以比朴素更好的方式进行,可能使用类似于this question中开发的策略。
请记住,x的条目都是正数并且已排序,因此x_k+k_j的条目也已排序。
附言:我正在寻找算法/语言不可知的想法。 C++标签主要用于在需要利用某些智能缓存策略时执行此操作。
编辑:
@liori提出了一个很好的观点,对于给定的i查找(j,k)对的时间复杂度为O(n),使用类似于回答相关问题的最后一次迭代的算法。问题在于是否可以比朴素地进行更高效地组合这些许多O(n)步骤。例如,我们可以在O(n)时间内找到给定索引i的(j,k)对。但是我们需要再次考虑j'<=j和k'<=k的所有条目作为下一个索引i'=i+1的候选项吗?这些节省的时间是否会累加?