使用 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
广告