有趣的排序问题

题目

有一个N个数的数组，将数组从小到大排序好。只允许下面这个操作：

• 任取数组中的一个数，然后将它放置在数组的最后一个位置。

问：最少操作多少次可以使得数组从小大有序?

思路

链接：https://www.nowcoder.com/questionTerminal/adc291e7e79f452c8b59243a5ce68d3a
来源：牛客网
链接：https://www.nowcoder.com/questionTerminal/adc291e7e79f452c8b59243a5ce68d3a
来源：牛客网

输入为 19 7 8 25 ，用 arr1表示
排序后 7 8 19 25 ，用 arr2 表示
都从数组第一个元素开始 ： 7 和 19 比较 ，7 < 19 ,
继续看arr1 的下一个元素 跟 arr2 的第一个元素 7 比较，此时 7 = 7 所以count++ ，
看两个数组后面的元素 ，都是 8 ，此时 count++ ，继续看 25 > 19 ，到此结束。
所以count = 2 。

/复杂度 nlogn 但是需要一个 n 的辅助数组
用一个辅助数组对所有元素进行排序，从小到大排序
从第一个排好序的元素开始，即最小的元素开始与没排好序数组元素比较，
检查有多少个已经是从最小到大好序的，位置可以不连续，但是大的元素必须在小的元素后面，

• 统计出一共有 count个，这些元素是不需要移动的元素
• 一共有 n 个元素，所以需要移动 n - count 次

大的元素，必须在小的后面，因此根据排序好的顺序来判断。
细节很多，好好思考。

代码

def minSteps(arrays):
    sortedArrays = sorted(arrays)
    length = len(arrays)
    minInd = 0
    for i in range(length):
        if sortedArrays[minInd] == arrays[i]:
            minInd += 1
    return length - minInd
n = int(input())
nums = [int(i) for i in input().split()]
print(minSteps(nums))