資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 統計排序陣列所需的“移至前端”操作的最小次數
給定一個包含 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。
整數變數 size 儲存陣列 Arr[] 的長度。
函式 movetoFront(int arr[], int n) 以陣列及其長度作為輸入，並返回對給定陣列進行排序所需的“移至前端”操作的最小次數。
Count 變數初始化為陣列的大小，因為在遞減順序陣列的情況下，所有元素都可以移動。
從最後一個索引開始遍歷並向前面移動，如果元素值與 count 相同（對於 1 到 n 之間的排序元素，n 是最後一個，n-1 是倒數第二個，依此類推），則遞減 count，因為該元素位於正確的位置。
這樣，在迴圈結束時，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
更新於： 2020-07-28
1K+ 次檢視
廣告