1에서 n 사이의 숫자 배열이 제공됩니다. 여기서 목표는 아니오를 찾는 것입니다. 주어진 배열을 정렬하는 데 필요한 '앞으로 이동' 작업. 배열에는 반복이 없습니다. 맨 앞으로 이동' 작업은 요소를 선택하고 첫 번째 위치(여기서는 인덱스 0)에 배치합니다.
요소가 올바른 위치에 있으면 끝에서 배열을 탐색합니다. 다른 이동은 필요하지 않습니다. 1에서 n까지의 요소에 대해 arr[i] 요소 배열의 올바른 위치는 인덱스 i+1보다 높아야 합니다. arr[0]은 1, arr[1]은 2, ....arr[n-1]은 n이어야 합니다.
입력
Arr[]= { 4,3,2,1 } 출력
Minimum move-to-front operations: 3
설명
Pull 3, 3,4,2,1 count=1 Pull 2, 2,3,4,1 count=2 Pull 1, 1,2,3,4 count=3
입력
Arr[]= { 6,1,2,5,4,3 } 출력
Minimum move-to-front operations: 5
설명
Pull 5, 5,6,1,2,4,3 count=1 Pull 4, 4,5,6,1,2,3 count=2 Pull 3, ,4,5,6,1,2 count=3 Pull 2, 2,3,4,5,6,1 count=4 Pull 1, 1,2,3,4,5,6 count=5
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 Arr[]은 1부터 n까지의 숫자를 저장합니다.
-
정수 변수 크기는 배열 Arr[]
의 길이를 저장합니다. -
함수 movetoFront(int arr[], int n)는 배열과 그 길이를 입력으로 받아 주어진 배열을 정렬하는 데 필요한 '맨 앞으로 이동' 작업의 최소 수를 반환합니다.
-
Count 변수는 배열의 크기로 초기화되며 배열의 순서가 감소할 경우 모든 요소를 이동할 수 있습니다.
-
마지막 인덱스에서 순회를 시작하고 앞쪽으로 이동합니다. 요소 값이 count와 같으면 (1에서 n 사이의 정렬된 요소의 경우 n이 마지막, n-1이 두 번째 마지막 등) 해당 요소만큼 카운트를 감소시킵니다. 올바른 위치에.
-
이런 식으로 루프의 끝에서 count는 원하는 결과를 얻습니다.
예시
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int movetoFront(int arr[], int n){
//take count as all elements are correctly placed
int count = n;
// Traverse array from end
for (int i=n-1; i >= 0; i--){
// If current item is at its correct position,
//decrement the count
//range is 1 to n so every arr[i] should have value i+1
//1 at 0 index, 2 at 1 index........
if (arr[i] == count)
count--;
}
return count;
}
int main(){
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout <<"Minimum 'move-to-front' to sort array:"<< movetoFront(Arr, size);
return 0;
} 출력
Minimum 'move-to-front' to sort array:6