难度: Medium
Submission
运行时间: 27 ms
内存: 16.4 MB
class Solution:
def findContestMatch(self, n: int) -> str:
team = [*range(1, n + 1)]
while n:
for i in range(n := n // 2):
team[i] = f"({team[i]},{team.pop()})"
return team[0]
Explain
这个题解使用了一种模拟配对过程的方法。初始化一个长度为n的列表team，保存了1到n的所有编号。然后进入循环，每次将列表中前一半元素和后一半元素配对，组成新的字符串形式，并不断更新到列表的前半部分。经过log(n)次循环后，最终列表中只剩下一个字符串，即为最终的配对结果。
时间复杂度: O(nlog(n))
空间复杂度: O(n)
class Solution:
def findContestMatch(self, n: int) -> str:
team = [*range(1, n + 1)] # 初始化编号列表
while n: # 循环直到只剩一个元素
for i in range(n := n // 2): # 遍历列表前一半元素
team[i] = f"({team[i]},{team.pop()})" # 将前半部分与后半部分配对
return team[0] # 返回最终结果
Explore
在每一轮循环中，队列team的长度会被更新为其一半，即通过`n := n // 2`更新。在循环体内，通过索引`i`从0遍历到`n - 1`（新的n值），并且每次循环中使用`team.pop()`从队列末尾取出元素。因为队列长度正好是更新前长度的一半，所以每次取出的元素正好是队列后半部分的元素。这样，循环中的每次配对都是前半部分的元素`team[i]`与取出的后半部分元素配对，确保了每一轮都能正确将前一半与后一半元素进行配对。
`team.pop()`方法从数组的末尾移除一个元素，并返回这个元素。这导致数组长度每次减一。由于我们每次循环都将n更新为其一半，而每次从末尾pop出的元素数量恰好等于新的n值，这保证了数组长度在每次循环后减半。这种影响对算法是可接受的，因为每轮配对后，需要的元素数量确实减少了一半，因为他们已经形成了新的配对关系，不再需要单独存在。
使用`n := n // 2`确实会更新n的值，使其减半，代表队列每次循环后新的有效长度。这种方式不会导致原数组长度信息的永久丢失，因为虽然n的值在循环中被更新，但这正是算法所需要的。算法通过不断减半n的值来逐步减少处理的元素数量，每次只处理当前n个元素。由于每次配对后，元素数量理应减半，这种处理方式恰好符合算法设计的需要。
如果n不是2的幂次方，算法仍然可以正常工作，因为每次循环中，元素数量都减半，直到n变为1。不是2的幂次方的情况下，最终在某次循环中，n将通过向下取整变为1，最后的配对将正常进行。这意味着无论n的初始值是多少，通过不断减半，最终都会配对到只剩一个元素，即最终的配对结果。因此，算法可以处理任意正整数n。