如何优化奇偶索引重排字符串函数，兼容int.MaxValue等超大count参数

核心思路 #

原代码的性能瓶颈在于逐次模拟重排过程，当count达到百万级甚至int.MaxValue时，O(count*n)的时间复杂度完全不可接受。我们可以利用置换映射的数学特性，跳过冗余的重复操作：

1. 每次重排本质是固定的位置置换，提前计算每个位置经过count次置换后的最终落点，一次构造结果即可，无需逐次迭代
2. 置换操作存在周期性，执行T次后会回到初始状态（T为置换循环节的最小公倍数），超大count可以先对T取模，直接降低到极小值

具体实现原理 #

假设字符串长度为n：

• 先统计偶数索引的总数 m = (n + 1) / 2
• 单次置换的位置映射规则：原位置i经过1次重排后的新位置为：
  • 若i是偶数：newIdx = i / 2
  • 若i是奇数：newIdx = m + (i - 1) / 2
• 对于任意位置i，我们可以直接递推出count次置换后的最终位置，无需逐次执行整个字符串的重排

优化后代码 #

public static string ShuffleChars(string source, int count)
{
    if (string.IsNullOrWhiteSpace(source))
    {
        throw new ArgumentException(nameof(source));
    }
    if (count < 0)
    {
        throw new ArgumentException(nameof(count));
    }
    int n = source.Length;
    // 边界情况：长度为1时重排无变化
    if (n == 1 || count == 0)
    {
        return source;
    }
    int m = (n + 1) / 2;
    char[] res = new char[n];
    bool[] visited = new bool[n];
    
    // 遍历所有循环节，计算count取模后的值，直接赋值
    for (int i = 0; i < n; i++)
    {
        if (visited[i]) continue;
        // 记录当前循环的所有位置
        List<int> cycle = new List<int>();
        int cur = i;
        while (!visited[cur])
        {
            visited[cur] = true;
            cycle.Add(cur);
            // 计算单次置换的下一个位置
            cur = cur % 2 == 0 ? cur / 2 : m + (cur - 1) / 2;
        }
        // 循环长度为cycle.Count，count取模后得到有效偏移
        int cycleLen = cycle.Count;
        int offset = count % cycleLen;
        // 直接按最终偏移赋值
        for (int j = 0; j < cycleLen; j++)
        {
            res[cycle[(j + offset) % cycleLen]] = source[cycle[j]];
        }
    }
    return new string(res);
}

优化效果对比 #

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