-1

我正在解决 GeeksforGeeks 上的一个问题，该问题涉及使用三个不同的数组元素作为三角形的边从大小为n的未排序数组arr[]中找到可能的三角形总数。这是上述问题的第一个实现。...

int findNumberOfTriangles(int arr[], int n)
    {
        // code here
        sort(arr,arr+n);
        
        int i,j,k,count=0;
        
        for(i=0;i<n-2;i++)//first side of triangle
        {
            k=i+2; // third side of triangle , ie. rightmost element initialized
            for(j=i+1;j<n;j++)    //second side of triangle
            {    
                // search for all elements less than sum of the 
                // first and second side of the triangle
                while(k<n)
                {
                    if(arr[i]+arr[j]>arr[k]) 
                        k++;                
                }
                
                count=count+ k-j-1; //adds no of triangle possible for each pair of sides
            }
        }
        
        return count;
    }

...上述实现是正确的，应该具有O(N^2)时间复杂度。对于上面的代码，我从 GeeksforGeeks 平台获得了一个TLE(Time Limit exceeded) ，预期时间限制=1.02 sec。

现在将以下实现与上述实现进行比较。

int findNumberOfTriangles(int arr[], int n)
        {
            // code here
            sort(arr,arr+n);
            
            int i,j,k,count=0;
            
            for(i=0;i<n-2;i++)//first side of triangle
            {
                k=i+2; // third side of triangle , ie. rightmost element initialized
                for(j=i+1;j<n;j++)    //second side of triangle
                {    
                    // search for all elements less than sum of the 
                    // first and second side of the triangle
                    while(k<n && arr[i]+arr[j]>arr[k])
                         k++; 
                    
                    count=count+ k-j-1; //adds no of triangle possible for each pair of sides
                }
            }
            
            return count;
        }

实现仅在第二个for 循环内的while 循环中有所不同。我通过使用逻辑 AND 操作将if 条件从while 主体内部移动到条件声明部分。时间复杂度与第一个实现相同：O(N^2)。

但是，这个实现被GeeksforGeeks接受，时间为 = (0/1.0)。

有人可以告诉我为什么两段等效代码之间存在如此大的性能差异。这是由于 GeeksforGeeks 平台还是由于 C++ 语言的特性。GeeksforGeeks 使用g++5.4编译器

链接：https ://practice.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1

4

1 回答 1

3

它们不是等价的。

            while(k<n)
            {
                if(arr[i]+arr[j]>arr[k]) 
                    k++;                
            }

在遇到的第一个 if 条件为 false 的元素上，此循环将永远继续循环，因为k不会递增。

这个：

      while(k<n && arr[i]+arr[j]>arr[k])
                     k++;

k<n当第一个元素或第一个元素为arr[i]+arr[j]>arr[k]假时停止循环。

考虑这个例子

          k            arr[i]+arr[j]>arr[k]
          1            true
          2            true 
          3            false 
         ...           false
          n

这首先计数k = 2，然后永远不会停止，因为k不再增加。第二个循环直到k = 2并在 时停止k = 3。

PS：（免责声明_我会告诉你我的个人观点，虽然它确实是）Geeksforgeeks 是一个寻找糟糕教程的好地方，有问题的代码通常是非标准的，但声称对初学者有好处（它不是) 和误导性且经常是错误的解释。错误也可能在这里发生，但通常可以修复某人的评论和答案（或者当他们太错误时投反对票）。如果您想学习 C++，我建议您改为：The Definitive C++ Book Guide and List

于 2021-07-14T20:26:19.977 回答