半有序排列

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. 第一个元素为1。
 * 2. 最后一个元素为n。
 * 需要统计1的位置和n的位置，然后计算它们需要移动的步数。
 * 如果1的位置在前，n的位置在后，中间位置无关紧要。
 * 使用Java Stream API实现
 */
import java.util.stream.IntStream;
public class Solution {
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int firstIndex = IntStream.range(0, n).filter(i -> nums[i] == 1).findFirst().getAsInt();
        int lastIndex = IntStream.range(0, n).filter(i -> nums[i] == n).findFirst().getAsInt();
        int steps1 = firstIndex;
        int stepsn = n - 1 - lastIndex;
        return firstIndex > lastIndex ? steps1 + stepsn - 1 : steps1 + stepsn;
    }
}

该题解的核心思路是通过计算将数字1和数字n移动到序列的首尾所需的最小交换次数。首先，找到数字1 (firstIdx) 和数字n (lastIdx) 在序列中的位置。如果数字1在数字n之前（firstIdx < lastIdx），则我们只需要分别将这两个数字移动到序列的两端。如果数字n在数字1之前（firstIdx > lastIdx），则在移动的同时需要多执行一次交换（omni为1），这是因为当1在n的右边时，将它们移到两端后，它们的相对位置仍然需要调整。最终的最小操作次数计算为firstIdx加上从lastIdx到序列末尾的距离，再减去omni。

O(n)

O(1)