基因组范围查询

Question

最近，我做了一项关于编码能力的培训--基因组范围查询(关于这场训练的细节，请参阅评估报告之一)。

解决这个问题的正确方法是使用前缀和。以下是实现：

struct Results solution(char *S, int P[], int Q[], int M) {
    struct Results result;
    int* ans = (int*)calloc(M, sizeof(int));
    int pre_sum_arr[strlen(S)][4];
    int i, j;

    memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
    for(i = 0 ; i < strlen(S) ; i++){
        if(S[i] == 'A') pre_sum_arr[i][0] = 1;
        else if(S[i] == 'C') pre_sum_arr[i][1] = 1;
        else if(S[i] == 'G') pre_sum_arr[i][2] = 1;
        else pre_sum_arr[i][3] = 1;
    }

    for(i = 1; i < strlen(S) ; i++){
        for(j = 0 ; j < 4 ; j++){
            pre_sum_arr[i][j] += pre_sum_arr[i - 1][j];
        }
    }

    for(i = 0 ; i < M ; i++){
        for(j = 0 ; j < 4 ; j++){
            if((P[i] == 0 && pre_sum_arr[Q[i]][j]) || \
               (pre_sum_arr[Q[i]][j] - pre_sum_arr[P[i] - 1][j] > 0)){
                ans[i] = j + 1;
                break;
            }
        }
    }

    result.A = ans;
    result.M = M;
    return result;
}

然而，评估报告说，它超过了大规模测试用例的时间限制(报告链接在上面)。

检测的时间复杂度为O(M * N)而不是O(M + N)。但在我看来，应该是O(M + N)，因为我独立地为N和M运行循环(计算前缀和的N，以及获得答案的M)。

对于这个问题，我也使用了另一种解决方案。我也认为它的复杂性是O(M + N)，但我得到了同样的结果。这是我的代码：

struct _pre_min_idx{
  int pre_1_idx;
  int pre_2_idx;
  int pre_3_idx;
};

int mapping(char c){
    if(c == 'A') return 1;
    if(c == 'C') return 2;
    if(c == 'G') return 3;
    if(c == 'T') return 4;
    return -1;
}

typedef struct _pre_min_idx pre_min_idx;

struct Results solution(char *S, int P[], int Q[], int M) {
    struct Results result;
    // A = 1, C = 2, G = 3, T = 4
    pre_min_idx pre_min_idx_arr[strlen(S)];
    int* min_nuc_arr = (int*)calloc(M, sizeof(int));
    int i;
    int pre_1_idx = -1, pre_2_idx = -1, pre_3_idx = -1;

    memset(pre_min_idx_arr, 0, sizeof(pre_min_idx_arr));
    for(i = 0 ; i < strlen(S) ; i++){
        if(S[i] == 'T'){
            pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
            pre_min_idx_arr[i].pre_2_idx = pre_2_idx;
            pre_min_idx_arr[i].pre_3_idx = pre_3_idx;
        }
        else if(S[i] == 'G'){
            pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
            pre_min_idx_arr[i].pre_2_idx = pre_2_idx;
            pre_min_idx_arr[i].pre_3_idx = -1;
            pre_3_idx = i;
        }
        else if(S[i] == 'C'){
            pre_min_idx_arr[i].pre_1_idx = pre_1_idx;
            pre_min_idx_arr[i].pre_2_idx = -1;
            pre_min_idx_arr[i].pre_3_idx = -1;
            pre_2_idx = i;
        }
        else{
            pre_min_idx_arr[i].pre_1_idx = -1;
            pre_min_idx_arr[i].pre_2_idx = -1;
            pre_min_idx_arr[i].pre_3_idx = -1;
            pre_1_idx = i;
        }
    }

    for(i = 0 ; i < M ; i++){
        pre_min_idx pmi_Q = pre_min_idx_arr[Q[i]];
        if(pmi_Q.pre_1_idx >= P[i])
            min_nuc_arr[i] = 1;
        else if(pmi_Q.pre_2_idx >= P[i])
            min_nuc_arr[i] = 2;
        else if(pmi_Q.pre_3_idx >= P[i])
            min_nuc_arr[i] = 3;
        else{
            min_nuc_arr[i] = mapping(S[Q[i]]);
        }
    }
    result.A = min_nuc_arr;
    result.M = M;
    return result;
}

评价报告为这里。

有人能帮我找出解决方案的问题吗？我被困了很久。任何性能改进技巧或建议将不胜感激。

Answer 1

strlen在字符串长度中需要一个线性时间。因此，for(i = 0 ; i < strlen(S) ; i++)将称它为n时间，其结果将是二次的。

更改这个和其他一些细节(将内容移到最小的范围内)，您将得到以下内容：

struct Results solution(char *S, int P[], int Q[], int M) {
    int len = strlen(S);
    int pre_sum_arr[len][4];

    memset(pre_sum_arr, 0, sizeof(pre_sum_arr));
    for(int i = 0 ; i < len ; i++){
             if(S[i] == 'A') pre_sum_arr[i][0] = 1;
        else if(S[i] == 'C') pre_sum_arr[i][1] = 1;
        else if(S[i] == 'G') pre_sum_arr[i][2] = 1;
        else                 pre_sum_arr[i][3] = 1;
    }

    for(int i = 1; i < len; i++){
        for(j = 0 ; j < 4 ; j++){
            pre_sum_arr[i][j] += pre_sum_arr[i - 1][j];
        }
    }

    int* ans = (int*)calloc(M, sizeof(int));
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < 4 ; j++){
            if((P[i] == 0 && pre_sum_arr[Q[i]][j]) || \
               (pre_sum_arr[Q[i]][j] - pre_sum_arr[P[i] - 1][j] > 0)){
                ans[i] = j + 1;
                break;
            }
        }
    }

    struct Results result;
    result.A = ans;
    result.M = M;
    return result;
}