https://leetcode.com/problems/semi-ordered-permutation/
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.Python
class Solution:
def semiOrderedPermutation(self, nums: List[int]) -> int:
idx1=nums.index(1)
idxn=nums.index(len(nums))
if idxn > idx1 :
return len(nums)-1-idxn+idx1
else:
return len(nums)-1-idxn+idx1-1그냥 직관적으로 간단하게 풀어봤다. accpet은 되었다는..!
보아하니 이게 최선인듯하다!
2. C
C는 딴 거 없고, python의 index기능을 for문으로 찾는게 좀 귀찮을 뿐이다.
int semiOrderedPermutation(int* nums, int numsSize){
int s;
int e;
for(int i=0;i<numsSize;i++){
if(nums[i]==1){
s=i;
break;
}
}
for(int i=0;i<numsSize;i++){
if(nums[i]==numsSize){
e=i;
break;
}
}
if(s<e) return numsSize-1-e+s;
return numsSize-1-e+s-1;
}
3. C++
C++도 이하동문
그냥 numsize 구하는게 C보다 편할 뿐이다. 진짜 C에서는 container에 element 개수도 일일히 새줘야 하는게 좀 짜친다..
define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
이런식으로 개수를 파악한다 -_-
class Solution {
public:
int semiOrderedPermutation(vector<int>& nums) {
int s;
int e;
int numsSize = nums.size();
for(int i=0;i<numsSize;i++){
if(nums[i]==1){
s=i;
break;
}
}
for(int i=0;i<numsSize;i++){
if(nums[i]==numsSize){
e=i;
break;
}
}
if(s<e) return numsSize-1-e+s;
return numsSize-1-e+s-1;
}
};