为什么此合并排序实现无法正常工作?

用户名

以下是我的合并排序实现,它执行的工作是获取一组整数对,并根据该对中的第二个元素对它们进行排序(关系被该对中的第一个元素打破,并且所有元素都是不同的)

void mer(vector<pair<int, int>> a, int l, int m, int r, vector<pair<int, int>> res) {
    int i = l;
    int j = m;
    int k = l;
    while (i < m && j < r) {
        if (a[i].second < a[j].second) {
            res[k] = a[i];
            i++;
            k++;
        } else
        if (a[i].second > a[j].second) {
            res[k] = a[j];
            j++;
            k++;
        } else {
            if (a[i].first > a[j].first) {
                res[k] = a[j];
                k++;
                j++;
            } else {
                res[k] = a[i];
                i++;
                k++;
            }
        }
    }
    while (i < m) {
        res[k] = a[i];
        k++;
        i++;
    }
    while (j < r) {
        res[k] = a[j];
        k++;
        j++;
    }
    for (int i = l; i < r; i++) {
        a[i] = res[i];
    }
}
    
void solve(vector<pair<int, int>> a, int l, int r, vector<pair<int, int>> res) {
    if (l < r) {
        int m = (l + r) / 2;
        solve(a, l, m, res);
        solve(a, m + 1, r, res);
        mer(a, l, m, r, res);
    }
}

但是当我使用main以下代码运行代码时

int main() {
    int n;
    cin >> n;
    map<int, int> a;

    for (int i = 0; i < n; i++) {
        int u;
        cin >> u;
        a[u]++;
    }
    vector<pair<int, int>> b;
    for (auto i : a) {
        b.push_back(i);
    }
    vector<pair<int, int>> res(b.size());
    solve(b, 0, b.size(), res);
}

认为我的输入是:

10
1 1 1 1 1 1 2 2 3 3
it outputs 
1 6
2 2
3 2

那就是输入输出是一样的。我花了很多时间寻找问题。我无法修复它。

chqrlie

您的代码中存在多个问题:

  • 这些vector对象应通过引用传递。

  • res不是solve()函数的目的地,而是充当的临时存储的辅助向量mer调用它tmp会减少混乱。

  • r索引中索引solve()被排除,因此对少于2个元素的切片的测试和递归调用应为:

    void mer(vector<pair<int, int>>& a, int l, int m, int r, vector<pair<int, int>>& res) {
        int i = l;
        int j = m;
        int k = l;
        while (i < m && j < r) {
            if (a[i].second < a[j].second) {
                res[k] = a[i];
                i++;
                k++;
            } else
            if (a[i].second > a[j].second) {
                res[k] = a[j];
                j++;
                k++;
            } else {
                if (a[i].first > a[j].first) {
                    res[k] = a[j];
                    k++;
                    j++;
                } else {
                    res[k] = a[i];
                    i++;
                    k++;
                }
            }
        }
        while (i < m) {
            res[k] = a[i];
            k++;
            i++;
        }
        while (j < r) {
            res[k] = a[j];
            k++;
            j++;
        }
        for (int i = l; i < r; i++) {
            a[i] = res[i];
        }
    }
    
    void solve(vector<pair<int, int>>& a, int l, int r, vector<pair<int, int>>& tmp) {
        if (r - l >= 2) {
            int m = (l + r) / 2;
            solve(a, l, m, tmp);
            solve(a, m, r, tmp);
            mer(a, l, m, r, tmp);
        }
    }
    
  • main()函数中,不要将输入值存储到对向量中,还应该打印排序后的对:

    int main() {
        int n;
        cin >> n;
    
        vector<pair<int, int>> a(n);
    
        for (int i = 0; i < n; i++) {
            a[i].first = i + 1;
            cin >> a[i].second;
        }
        vector<pair<int, int>> tmp(n);
        solve(a, 0, n, tmp);
        for (int i = 0; i < n; i++) {
            printf("%d %d\n", a[i].first, a[i].second);
        }
        return 0
    }
    

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章