Make writing a habit together! This is the fifth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

Matches [I] = [Winneri, loseri] indicates that Winneri defeated Loseri in a match.

Return a list of length 2 **answer:

  • answer[0]Is that allThere is noList of players who have lost any matches.
  • answer[1]It’s all that happens to loseaList of players for the match.

The values in both lists should be returned in ascending order.

Note:

  • Consider only players who have played at least one match.
  • Generated test cases ensure that no two matches have the same result.

Title link: Players who have lost zero or one match.

Two, the title requirements

The sample

Input: matches = [[1, 3], [2, 3], [3], [5, 6], [5, 7], [4, 5], [4, 8], [4, 9], [10, 4], [10, 9]] output: [,2,10 [1], [4,5,7,8]] : Players 1, 2, and 10 did not lose any matches. Players 4, 5, 7 and 8 each lose a match. Players 3, 6, and 9 each lost two matches. Therefore, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].Copy the code

inspection

1. Hash and weight judgment 2. Recommended time: 15-35minCopy the code

Third, problem analysis

This is actually pretty straightforward, but my initial idea was to use a hash table to count the people who lost.

If you lose 0 games, you just decide whether the player who won the game is in the game or not, and if you lose a game, you just decide that the value of the hash table is 1.

However, there is a drawback to this method. It takes too long to execute, and the winner needs to be judged again to prevent repeated joining.

Start optimizing!

Maps can be sorted automatically, so use map output storage this time. We first store the winning player in the map and set the initial value to 0. Then store the lost player to the map, and all we need to do is determine 0 and 1.

Four, coding implementation

1. Before optimization

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        map<int.int>l,k;// Map stores the number of lost races
        int i,j,m=matches.size(a);// Initialize the data
        vector<int>ans1,ans2;// Store them separately
        for(i=0; i<m; i++) l[matches[i][1]] + +;// Count the number of matches lost
        for(i=0; i<m; i++) {if(l[matches[i][0= =]]0&&k[matches[i][0= =]]0)/ / not to lose
            {
                ans1.push_back(matches[i][0]);
                k[matches[i][0]] =1;// It is used to judge the weight
            }
            if(l[matches[i][1= =]]1&&k[matches[i][1= =]]0)// Only one loss
            {
                   ans2.push_back(matches[i][1]);
                   k[matches[i][1]] =1;// It is used to judge the weight}}sort(ans1.begin(),ans1.end());/ / sorting
        sort(ans2.begin(),ans2.end());/ / sorting
        return {ans1,ans2};// Output the result}};Copy the code

2. After the optimization

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) {
        map<int.int>m;/ / define the map
        vector<int>ans1,ans2;
        int i,n=matches.size(a);// Initial data
        for(i=0; i<n; i++)// Store the number of wins and set it to 0
            m[matches[i][0]] =0;
        for(i=0; i<n; i++)// The number of storage inputs ++
            m[matches[i][1]] + +;for(auto j=m.begin(a); j! =m.end(a); j++)// Store the output inside the map loop
        {
            if(j->second==0)/ / to zero
                ans1.push_back(j->first);// Store players that did not lose
            else if(j->second==1)/ / 1
                ans2.push_back(j->first);// Save players who have lost only one match
        }
        return{ans1,ans2}; }};Copy the code

V. Test results

The code is much simpler, execution time is still very long, next time to optimize it.