leetcode
leetcode 501 ~ 550
输出比赛匹配对

输出比赛匹配对

难度:

标签:

题目描述

代码结果

运行时间: 27 ms, 内存: 16.4 MB


/*
 * 思路:
 * 1. 使用Java Stream来简化代码。
 * 2. 每轮比赛通过Stream进行配对,生成匹配对列表。
 * 3. 胜者进入下一轮,直至决出冠军。
 */
 
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class MatchOutputStream {
    public List<List<String>> findContestMatch(int[] teams) {
        List<String> currentRound = Arrays.stream(teams)
                                          .mapToObj(String::valueOf)
                                          .collect(Collectors.toList());
        List<List<String>> result = new ArrayList<>();
        while (currentRound.size() > 1) {
            List<String> pairs = IntStream.range(0, currentRound.size() / 2)
                                          .mapToObj(i -> "(" + currentRound.get(i) + "," + currentRound.get(currentRound.size() - 1 - i) + ")")
                                          .collect(Collectors.toList());
            result.add(pairs);
            currentRound = pairs;
        }
        return result;
    }
 
    public static void main(String[] args) {
        MatchOutputStream mo = new MatchOutputStream();
        int[] teams = {1, 2, 3, 4, 5, 6, 7, 8};
        List<List<String>> matches = mo.findContestMatch(teams);
        for (List<String> round : matches) {
            System.out.println(round);
        }
    }
}
 

解释

方法:

这个题解使用了一种模拟配对过程的方法。初始化一个长度为n的列表team,保存了1到n的所有编号。然后进入循环,每次将列表中前一半元素和后一半元素配对,组成新的字符串形式,并不断更新到列表的前半部分。经过log(n)次循环后,最终列表中只剩下一个字符串,即为最终的配对结果。

时间复杂度:

O(nlog(n))

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到的模拟配对过程,是如何确保每一轮都能正确地将前一半与后一半元素进行配对的?
在每一轮循环中,队列team的长度会被更新为其一半,即通过`n := n // 2`更新。在循环体内,通过索引`i`从0遍历到`n - 1`(新的n值),并且每次循环中使用`team.pop()`从队列末尾取出元素。因为队列长度正好是更新前长度的一半,所以每次取出的元素正好是队列后半部分的元素。这样,循环中的每次配对都是前半部分的元素`team[i]`与取出的后半部分元素配对,确保了每一轮都能正确将前一半与后一半元素进行配对。
🦆
在数组的修改过程中,使用`team.pop()`来配对,这种做法对数组长度有什么影响?为什么这种影响对算法是可接受的?
`team.pop()`方法从数组的末尾移除一个元素,并返回这个元素。这导致数组长度每次减一。由于我们每次循环都将n更新为其一半,而每次从末尾pop出的元素数量恰好等于新的n值,这保证了数组长度在每次循环后减半。这种影响对算法是可接受的,因为每轮配对后,需要的元素数量确实减少了一半,因为他们已经形成了新的配对关系,不再需要单独存在。
🦆
在while循环中使用`n := n // 2`进行更新,这种更新方式是否可能导致原数组的长度信息丢失,如果是,算法是如何处理的?
使用`n := n // 2`确实会更新n的值,使其减半,代表队列每次循环后新的有效长度。这种方式不会导致原数组长度信息的永久丢失,因为虽然n的值在循环中被更新,但这正是算法所需要的。算法通过不断减半n的值来逐步减少处理的元素数量,每次只处理当前n个元素。由于每次配对后,元素数量理应减半,这种处理方式恰好符合算法设计的需要。
🦆
给定题解的算法结构,若`n`不是2的幂次方,算法的行为会有什么变化?
如果n不是2的幂次方,算法仍然可以正常工作,因为每次循环中,元素数量都减半,直到n变为1。不是2的幂次方的情况下,最终在某次循环中,n将通过向下取整变为1,最后的配对将正常进行。这意味着无论n的初始值是多少,通过不断减半,最终都会配对到只剩一个元素,即最终的配对结果。因此,算法可以处理任意正整数n。

相关问题