主页 / user-28334844

AK1557's questions

Martin Hope
AK1557
Asked: 2024-11-17 23:16:11 +0800 CST
  • 6

我已经编写了代码，也许是一个简单的编码测试。（详情如下）

拳击手进行比赛

更优秀的人总是会赢 例如）如果 A 拳击手比 B 更优秀，那么 A 总是会赢 B 如果 C 拳击手比 A 更优秀，那么 C 总是会赢 A、B

So, always (C > A > B), never (C > A > B > C) things.

比赛结束后，部分比赛结果缺失。根据现有结果，确定有多少名拳击手可以确定排名。

*constrains
i)  1 <= boxers <= 100.
ii)  1 <= results.size() <= 4500, results contains match_data.
iii) match_data [A, B] means (A defeated B).
iV) no contradictions in the data: if [A,B] exist, [B,A] does not.

----------------------------------------------------------------------

N of boxer                       results                          answer

    5             [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]      2

-----------------------------------------------------------------------

                        [[  explain  ]]

在这种情况下，您可以构建两个排名链。

4 > 3 > 2 > 5 1 > 2 > 5

这里，2、5 可以分别确认他们的排名为第 4、第 5，但是，4、3、1 由于缺少数据而无法确认他们的相对排名。

因此答案是2；

下面是我的代码

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int win = 0;
int lose = 1;

int solution(int n, vector<vector<int>> results) {

    queue<pair<int, int>> q;

    vector<vector<vector<int>>> Graph(n, vector<vector<int>>(2));

    vector<int> rating = vector(n,0);

    vector<vector<vector<int>>> List(n, vector<vector<int>>(2, vector<int>(n, 0)));


    for(int match=0; match < results.size(); match++){

        int winner = results[match][win]-1;
        int loser = results[match][lose]-1;

        Graph[winner][win].push_back(loser);
        Graph[loser][lose].push_back(winner);
    
    }

    for(int index=0; index<n; index++){
    
        if(Graph[index][win].size() == 0 && Graph[index][lose].size() == 0) return 0;
    
        if(Graph[index][win].size() == 0){
            for(int i=0; i<Graph[index][lose].size(); i++){
                q.push({Graph[index][lose][i], index});
            }
            while(!q.empty()){
                auto [winner, loser] = q.front();
                q.pop();
            
                if(List[winner][win][loser]==0){
                    List[winner][win][loser] = 1;
                    rating[winner]++;
                }
            
            
                for(int j=0; j<n; j++){
                    if(List[loser][win][j] == 1 && List[winner][win][j] == 0){
                        List[winner][win][j] = 1;
                        rating[winner]++;
                    }
                }
            
                for(int j=0; j<Graph[winner][lose].size(); j++){
                    q.push({Graph[winner][lose][j], winner});
                }
            }
        }
    
        if(Graph[index][lose].size() == 0){
            for(int i=0; i<Graph[index][win].size(); i++){
                q.push({Graph[index][win][i], index});
            }
         
            while(!q.empty()){
                auto [loser, winner] = q.front();
                q.pop();
                
                if(List[loser][lose][winner]==0){
                    List[loser][lose][winner] = 1;
                    rating[loser]++;
                }
                
            
                for(int j=0; j<n; j++){
                    if(List[winner][lose][j] == 1 && List[loser][lose][j] == 0){
                        List[loser][lose][j] = 1;
                        rating[loser]++;
                    }
                }
            
                for(int j=0; j<Graph[loser][win].size(); j++){
                    q.push({Graph[loser][win][j], loser});
                }
            }
        }
    }

    int answer = 0;
    for(int index=0; index<n; index++){
        //cout << rating[index] << ", ";
        if(rating[index]==n-1){
            answer++;
        }
    }

    return answer;

}

我的代码可以运行，并且我预计代码复杂度为 O(n^2+n⋅m) << n = boxer number, m = results.size() >>

当输入大量数据时，它仍然有效，但需要很长时间。

我发现 Floyd-Warshall 算法效果更好。

即便如此，我还是真的很想知道为什么我的代码花费了这么多时间以及它的实际时间复杂度是多少。

  1. 感谢您花时间阅读并提供帮助。
c++17