使用C ++使所有元素相等的最小移动次数

  • Z时代
  • 2024-01-10
  • 分类：综合

问题陈述

给定一个由N个元素和整数K组成的数组，则可以在给定的数组上多次执行以下操作-

  • 在数组末尾插入第K个元素，然后删除数组的第一个元素。

任务是找到使数组的所有元素相等所需的最小移动次数。如果不可能，则打印-1

If arr[] = {1, 2, 3, 4, 5, 6} and k = 6 then minimum 5 moves are
required:
Move-1: {2, 3, 4, 5, 6, 6}
Move-2: {3, 4, 5, 6, 6, 6}
Move-3: {4, 5, 6, 6, 6, 6}
Move-4: {5, 6, 6, 6, 6, 6}
Move-5: {6, 6, 6, 6, 6, 6}

算法

1.首先我们将a[k]复制到末尾，然后复制a[k + 1]，依此类推
2.为确保只复制相等的元素，K到N范围内的所有元素都应相等。 我们需要删除1到K范围内所有不等于a[k]的元素
3.继续应用运算，直到我们达到范围1到K中最右边的项，不等于a[k]。

示例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinMoves(int *arr, int n, int k){
   int i;
   for (i = k - 1; i < n; ++i) {
      if (arr[i] != arr[k - 1]) {
         return -1;
      }
   }
   for (i = k - 1; i >= 0; --i) {
      if (arr[i] != arr[k - 1]) {
         return i + 1;
      }
   }
   return 0;
}
int main(){
   int arr[] = {1, 2, 3, 4, 5, 6};
   int k = 6;
   cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它生成以下输出-

Minimum moves required = 5

以上是 使用C ++使所有元素相等的最小移动次数 的全部内容， 来源链接： utcz.com/z/335302.html

回到顶部