315K排序算法最小操作次数计算

题目解析

给定一个长度为 n 的排列，使用 K 排序算法可以通过以下步骤将其从小到大排序：每次从数列中选择最多 K 个位置的数，将它们移除后，将剩余的数左对齐。接着对移除的数进行排序，并将它们放在数列的末尾。需要计算最少需要多少次这样的操作，才能使数列按升序排列。

需要计算最少需要多少次这样的操作，才能使数列按升序排列。

解题思路

1. 确定从头开始的最长连续递增子序列：

   • 遍历数组，找到数列中按顺序排列的最长连续递增子序列。这部分元素在最终排序中不需要移动。
   • 记录当前序列中下一个期望出现的数值 i，初始为 1。
   • 如果当前遍历的数 x 等于 i，则 i 增加一，表示下一个期望的数值。

2. 计算最少操作次数：

   • 总需要移动的元素数为 n - (i - 1)，即总元素数减去已经按序排列的最长连续子序列的长度。
   • 每次操作最多可以移动 K 个元素，因此最少的操作次数为 ceil((n - (i - 1)) / K)。为了避免使用浮点运算，可以使用 (move + K - 1) // K 来实现向上取整。

代码实现

def solution(n: int, k: int, a: list) -> int:
    i = 1
    for x in a:
        if i == x:
            i += 1
    return (n - i + k) // k

if __name__ == '__main__':
    print(solution(n = 5, k = 1, a = [1, 2, 3, 4, 5]) == 0)
    print(solution(n = 5, k = 2, a = [1, 3, 5, 4, 2]) == 2)
    print(solution(n = 6, k = 3, a = [6, 5, 3, 1, 4, 2]) == 2)

复杂度分析

• 时间复杂度：O(n)，其中 n 是数列的长度。遍历数列一次即可找到最长连续递增子序列。
• 空间复杂度：O(1)，只使用了常数空间。