資料結構
網路
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 次瀏覽
廣告