数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究使用 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. First we copy a[k] to the end, then a[k+1] and so on 2. To make sure that we only copy equal elements, all elements in the range K to N should be equal. We need to remove all elements in range 1 to K that are not equal to a[k] 3. Keep applying operations until we reach the rightmost term in range 1 to K that is not equal to 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
更新日期：2019-10-31
193 次浏览
广告