题目 #

You are given a 0-indexed permutation of n integers nums.

A permutation is called semi-ordered if the first number equals 1 and the last number equals n. You can perform the below operation as many times as you want until you make nums a semi-ordered permutation:

• Pick two adjacent elements in nums, then swap them.

Return the minimum number of operations to make nums a semi-ordered permutation.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.

Example 1:

Input: nums = [2,1,4,3]
Output: 2
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
2 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than two operations that make nums a semi-ordered permutation.

Example 2:

Input: nums = [2,4,1,3]
Output: 3
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 1 and j = 2. The permutation becomes [2,1,4,3].
2 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
3 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than three operations that make nums a semi-ordered permutation.

Example 3:

Input: nums = [1,3,4,2,5]
Output: 0
Explanation: The permutation is already a semi-ordered permutation.

Constraints:

• 2 <= nums.length == n <= 50
• 1 <= nums[i] <= 50
• nums is a permutation.

思路1 分析+数学计算 #

分析 #

• 只要第一个和最后一个对上即可，那么计算一下第一个和最后一个差多少步，走过去即可
• 注意走的过程中，如果两个数交换了，需要减去一步

代码 #

 1func semiOrderedPermutation(nums []int) int {
 2	// 先找到1和n的位置
 3	index1, indexn := 0, 0
 4	n := len(nums)
 5	for i, v := range nums {
 6		if v == 1 {
 7			index1 = i
 8		} else if v == n {
 9			indexn = i
10		}
11	}
12
13	sum := (index1 - 0) + (n - 1 - indexn)
14	if index1 > indexn {
15		sum--
16	}
17	return sum
18}