Hackerrank《Small Triangles, Large Triangles》代码仅过样例求排查

要求按三角形面积从小到大排序后，输出各三角形的三条边长。以下是提交的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle
{
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle* tr, int n) {
    /**
    * Sort an array a of the length n
    */
    double arr[n+1];
    
    triangle temp;
 
    for(int i=0;i<n;i++)
    {
        double area_2,p;
        p=((tr[i].a+tr[i].b+tr[i].c)/2.0);
        area_2=(p*(p-tr[i].a)*(p-tr[i].b)*(p-tr[i].c));
        arr[i]=area_2;
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(arr[i]>arr[j])
            {
               temp=tr[i];
                tr[i]=tr[j];
                tr[j]=temp;
            }
            
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    return 0;
}

核心问题原因 #

排序逻辑存在漏洞：当交换tr数组中的三角形元素时，没有同步交换arr数组中对应的面积平方值。这会导致后续循环比较时，arr数组的元素与tr数组的三角形不再一一对应，排序判断完全失效，最终输出错误的排序结果。

比如，假设第一次交换了tr[i]和tr[j]，但arr[i]和arr[j]仍保持原值，后续循环比较arr时，用的还是最初的面积平方数据，和当前tr数组的三角形不匹配，自然无法得到正确的排序。

修正方案 #

在交换三角形结构体的同时，同步交换arr数组中对应的元素：

if(arr[i]>arr[j])
{
   // 交换三角形
   temp=tr[i];
   tr[i]=tr[j];
   tr[j]=temp;
   // 同步交换面积平方值
   double temp_area = arr[i];
   arr[i] = arr[j];
   arr[j] = temp_area;
}

修正后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle
{
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle* tr, int n) {
    double arr[n];
    
    triangle temp;
 
    for(int i=0;i<n;i++)
    {
        double p = (tr[i].a + tr[i].b + tr[i].c) / 2.0;
        double area_sq = p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c);
        arr[i] = area_sq;
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(arr[i]>arr[j])
            {
               temp=tr[i];
                tr[i]=tr[j];
                tr[j]=temp;
                // 新增交换面积平方的代码
                double temp_area = arr[i];
                arr[i] = arr[j];
                arr[j] = temp_area;
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    free(tr); // 新增内存释放，避免内存泄漏
    return 0;
}

额外优化：原代码中arr定义为double arr[n+1];，实际只用到前n个元素，修正后改为double arr[n];更严谨；同时在main函数中新增free(tr);释放动态分配的内存，避免内存泄漏。

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