Python约瑟夫排列O(n²)时间复杂度优化方案咨询

原代码性能瓶颈 #

你的代码核心问题在于array.pop(index)操作：Python的list基于动态数组实现，删除中间元素时需要将后续所有元素向前移动，单次操作时间复杂度为O(n)，循环n次后整体时间复杂度达到O(n²)，当n规模扩大到万级以上时，耗时会急剧上升。

优化方案 #

方案1：使用SortedList（第三方库，快速实现） #

如果可以引入第三方库sortedcontainers，它的SortedList提供O(logn)时间复杂度的pop(index)操作，直接替换原代码的list即可，几乎无需修改逻辑：

from sortedcontainers import SortedList

def solution(array, k):
    permutation = []
    sl = SortedList(array)
    index = 0
    while sl:
        index = (index + k - 1) % len(sl)
        permutation.append(sl.pop(index))
    return permutation

# 测试
people = 8
arr = [p+1 for p in range(people)]
k = 3
print(solution(arr, k))  # 输出: [3, 6, 1, 5, 2, 8, 4, 7]

该方案时间复杂度为O(nlogn)，处理十万级数据也能快速完成。

方案2：手动实现线段树（无第三方库依赖） #

若无法使用第三方库，可以实现线段树维护剩余元素的数量，快速定位并删除第k个元素，每次操作时间复杂度为O(logn)：

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.tree = [0] * (2 * self.n)
        # 初始化叶子节点：1表示元素存在
        for i in range(size):
            self.tree[self.n + i] = 1
        # 构建线段树
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
    
    def query(self, k):
        # 找到第k个剩余元素的索引（0-based）
        node = 1
        while node < self.n:
            left_count = self.tree[2*node]
            if k < left_count:
                node = 2*node
            else:
                k -= left_count
                node = 2*node + 1
        return node - self.n
    
    def update(self, idx):
        # 标记idx位置的元素已删除
        node = self.n + idx
        self.tree[node] = 0
        node >>= 1
        while node >= 1:
            self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
            node >>= 1

def solution(array, k):
    permutation = []
    n = len(array)
    st = SegmentTree(n)
    pos = 0
    for m in range(n, 0, -1):
        pos = (pos + k - 1) % m
        idx = st.query(pos)
        permutation.append(array[idx])
        st.update(idx)
    return permutation

# 测试
people = 8
arr = [p+1 for p in range(people)]
k = 3
print(solution(arr, k))  # 输出: [3, 6, 1, 5, 2, 8, 4, 7]

该方案同样为O(nlogn)时间复杂度，完全依赖Python标准库，适合生产环境使用。

方案3：针对连续整数输入的简化 #

如果你的输入是连续整数（如1到n），可以简化逻辑，但注意该方案本质仍为O(n²)，仅代码更简洁，不适用于大规模数据：

def josephus_permutation(n, k):
    permutation = []
    people = list(range(n))
    pos = 0
    for m in range(n, 0, -1):
        pos = (pos + k - 1) % m
        permutation.append(people.pop(pos) + 1)  # 转为1-based编号
    return permutation

# 测试
print(josephus_permutation(8, 3))  # 输出: [3, 6, 1, 5, 2, 8, 4, 7]

内容的提问来源于stack exchange，提问作者Sajal