[Leetcode] 2717. Semi-Ordered Permutation (Easy)

概述

題目

https://leetcode.com/problems/semi-ordered-permutation/
相鄰兩兩互換，最終使 1 在首位、n 在末位之最小次數

心得

很直覺式題目，確認交換次數有無交錯即可得到最終結果 (次數)

Math

思路

只分成 1, n 交錯與不交錯，前者會因為 1 次而讓 1, n 都向正確位置前進，故 -1；後者則正常計算次數

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def semiOrderedPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if nums[0] == 1 and nums[-1] == n:
            return 0

        # first, second 分別代表 1 與 n 的位置
        f, s = nums.index(1), nums.index(n)
        if f<s:
            return f-1 + n-s
        return f-1 + n-s-1

Complexity

Time Complexity: O(n)
只在橫向 n 個數中操作，故 O(n)

Space Complexity: O(1)
基本上無使用到額外空間