排序次数

[编程题]排序次数

热度指数：1515 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小摩有一个N个数的数组，他想将数组从小到大排好序，但是萌萌的小摩只会下面这个操作：

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

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

输入描述:

首先输入一个正整数N，接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)

输出描述:

输出一行操作数

示例1

输入

4
19 7 8 25

输出

说明

19放到最后，25放到最后，两步完成从小到大排序

算法知识视频讲解

Python

白色纯度

O(n)时间复杂度，找到最小的元素，遍历后面的元素即可！

本来就是解决排序的问题，你来个先排序再处理有点画蛇添足了。

不需要对原数组排序，只需要找到原数组最小的元素后面有多少个顺序元素的数量即可。

因为最小的元素后面的顺序元素不需要额外操作来排序，所以其余的元素都是要额外操作来排序的。

def solve(num):
    x = num.index(min(num))
    stack = [num[x]]
    while x<len(num):
        if num[x]>=stack[-1]:
            stack.append(num[x])
        x += 1
    return len(num)-len(stack)+1
if __name__=='__main__':
    n = int(raw_input().strip())
    num = list(map(int,raw_input().split()))
    print(solve(num))

编辑于 2019-09-12 16:37:05 回复(0)