2016 Bronze January p3

题目

一个升序序列中有一个不符合升序条件的元素，每次交换两个元素，求使序列恢复升序最小的步骤数

思路

先找到不符合要求元素的位置和它应该在的位置，然后从该元素位置向原位置遍历，途中若某元素与上一个元素不相同，则步骤数加一。

复杂度分析

找到不符合要求元素位置和原位置的复杂度均为 O(n)，遍历的复杂度也为 O(n)，因此总复杂度为 O(n)。元素数量最大为 100，因此不会超时。