时间戳

首页 > 解决方案 > 在求解可能的三角形总数时使用 for 和 while 的差异

java - 在求解可能的三角形总数时使用 for 和 while 的差异

问题描述

我在 Codility 中遇到过这个问题。请参阅此链接。我设法解决了这个问题。然而，这给我留下了一些疑问。

这是使用三个for.

public int solution(int[] A) {
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        for (int j = i + 1; j < A.length - 1; j++){
            for (k = j + 1; k < A.length; k++){
                if (A[i] + A[j] > A[k]) break;
            count += k - j - 1;
        }
    }
    return count;
}

这是while在最里面使用的代码for。

public int solution(int[] A) {
    // write your code in Java SE 8
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        k = i + 2;
        for (int j = i + 1; j < A.length; j++){
            while (k < A.length && A[i] + A[j] > A[k]) {
                k++;
            }
            count += k - j - 1;
        }
    }
    return count;
}

上面的第一个解决方案在 Codility 中并没有给我满分，因为在大型测试用例中编译需要很长时间。但是，在使用 的第二个解决方案中while，我得到了满分。即使我在上面的这两个代码中都添加了三角形检查，为什么会出现这种情况？for和这些有关系吗while？

我也确实从第二个解决方案中了解了时间复杂度。这是链接。k变量的初始化方式有所不同。这种差异是否会对这两个代码的性能产生巨大影响？

我试图弄清楚这两个代码之间的区别。

标签： javaalgorithmtime-complexity

解决方案

for loop与上述while loop这些解决方案无关。事实上，我们可以修改第二个解决方案，使while循环for如下所示：

 public int solution(int[] A) {
        Arrays.sort(A);
        int k, count = 0;
        for (int i = 0; i < A.length - 2; i++) {
            k = i + 2;
            for (int j = i + 1; j < A.length; j++) {
                for( ; k < A.length; k++) {
                    if ( (A[i] + A[j]) <= A[k]) break;
                }
                count += k - j - 1;
            }
        }
        return count;
    }

实际上，您的两种解决方案背后的主要逻辑是完全不同的。

在第一个解决方案中：
我们正在使用三个 for 循环修复所有可能的三元组，并在前两个最小长度对的总和小于或等于第三个的总和时打破第三个循环，即应该是"if (A[i] + A[j] <= A[k]) break;"。因此，整体时间复杂度将为O(n^3)。

在第二种解决方案中：
我们只修复两个for loops并执行计算。for loop代码中的 while 循环每次using只运行一次i。由于数组被排序了一次，这个解决方案背后的想法是，如果我们使用前两个值配对两个值for loops，并且索引处的值的总和是i，即如果它在索引处遇到大于或等于的值，则为下一对和，第三个索引肯定会大于前一个，因为索引处的值大于索引处的值，即。所以，第三个索引肯定比前面那个在右边jsumsum = A[i] + A[j]ksumij + 1kj + 1jA[j] <= A[j + 1]k. 因此，第二种解决方案的总体复杂度为O(n^2)。

推荐阅读