使用C ++使所有元素相等的最小移动次数
问题陈述
给定一个由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