c - C 中的 Triplet Codility - 仅获得 11%(训练)

Question

我对 C 还很陌生，并且部分地通过 Codility 培训来学习它。

对于三重问题，我只得到 11% 我不确定这里有什么问题。问题是:给定一个由 N 个整数组成的非空零索引数组 A。三元组 (P, Q, R) 的乘积等于 A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N)。

您的目标是找到任何三元组的最大乘积。

写一个函数:

int solution(int A[], int N); 

给定一个非空的零索引数组 A，返回任何三元组的最大乘积的值。 例如，给定数组 A 这样:

A[0] = -3
A[1] = 1
A[2] = 2
A[3] = -2
A[4] = 5
A[5] = 6 

函数应返回 60，因为三元组 (2, 4, 5) 的乘积最大。

假设: •N为[3..100,000]范围内的整数； •数组A的每个元素都是[−1,000..1,000]范围内的整数。

复杂性: •预期的最坏情况时间复杂度为O(N*log(N))； •预期的最坏情况空间复杂度为 O(1)，超出输入存储空间(不包括输入参数所需的存储空间)。

我的代码给了我 11%，我想知道这段代码哪里出了问题。我首先对矩阵进行排序，然后比较三个最大的正数和 2 个最大的负数以及最大的正数:

int solution(int A[], int N) {
    int i,j,PQR_pos,PQR_neg, temp;

    for (i=0; i<N; i++) { 
        for (j=0; j<N-i; j++) 
            if (A[j+1] < A[j]) { /* compare the two neighbours */ 
                temp = A[j]; /* swap a[j] and a[j+1] */ 
                A[j] = A[j+1]; 
                A[j+1] = temp; 
            } 
    }

    PQR_pos = A[N] * A[N-1] * A[N-2];
    PQR_neg = A[N] * A[1] * A[0];

    if (PQR_pos>PQR_neg) return PQR_pos;
    else return PQR_neg;

}

Answer 1

你根本不需要排序。

首先对输入数组进行一次线性扫描，存储最大的3个和最小的2个(且小于零)，则结果为:
max(
最大 * 第二大 * 第三大 ,
最大 * 最低 * 2nd_lowest)

利用所有数字都在 [-1000..1000] 中这一事实，您甚至不需要编码。只需在数组中计数并存储最大和最小索引，在扫描输入数组后只需扫描计数数组即可找到所有 5 个需要的数字。