使用 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+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告