資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用單個移動將陣列元素移動 k 個位置？
假設我們有一個數組，其中包含從 1 到 n 的 n 個元素，但順序被打亂了。還給定一個整數 K。有 N 個人排隊打羽毛球。前兩位選手開始比賽，然後輸的人回到隊伍末尾。贏的人繼續與隊伍中的下一位選手比賽，以此類推。他們會一直比賽，直到某個人連續贏 K 次。然後，該選手成為最終獲勝者。
如果佇列類似於 [2, 1, 3, 4, 5] 且 K = 2，則輸出將為 5。現在檢視解釋 -
(2, 1) 比賽，2 獲勝，所以 1 將被新增到佇列中，佇列變為 [3, 4, 5, 1] (2, 3) 比賽，3 獲勝，所以 2 將被新增到佇列中，佇列變為 [4, 5, 1, 2] (3, 4) 比賽，4 獲勝，所以 3 將被新增到佇列中，佇列變為 [5, 1, 2, 3] (4, 5) 比賽，5 獲勝，所以 4 將被新增到佇列中，佇列變為 [1, 2, 3, 4] (5, 1) 比賽，5 獲勝，所以 3 將被新增到佇列中，佇列變為 [2, 3, 4, 1]
(2, 1) 比賽，2 獲勝，所以 1 將被新增到佇列中，佇列變為 [3, 4, 5, 1]
(2, 3) 比賽，3 獲勝，所以 2 將被新增到佇列中，佇列變為 [4, 5, 1, 2]
(3, 4) 比賽，4 獲勝，所以 3 將被新增到佇列中，佇列變為 [5, 1, 2, 3]
(4, 5) 比賽，5 獲勝，所以 4 將被新增到佇列中，佇列變為 [1, 2, 3, 4]
(5, 1) 比賽，5 獲勝，所以 3 將被新增到佇列中，佇列變為 [2, 3, 4, 1]
由於 5 連續贏了兩場比賽，所以輸出為 5。
演算法
winner(arr, n, k)
Begin if k >= n-1, then return n best_player := 0 win_count := 0 for each element e in arr, do if e > best_player, then best_player := e if e is 0th element, then win_count := 1 end if else increase win_count by 1 end if if win_count >= k, then return best player done return best player End
示例
#include <iostream>
using namespace std;
int winner(int arr[], int n, int k) {
if (k >= n - 1) //if K exceeds the array size, then return n
return n;
int best_player = 0, win_count = 0; //initially best player and win count is not set
for (int i = 0; i < n; i++) { //for each member of the array
if (arr[i] > best_player) { //when arr[i] is better than the best one, update best
best_player = arr[i];
if (i) //if i is not the 0th element, set win_count as 1
win_count = 1;
}else //otherwise increase win count
win_count += 1;
if (win_count >= k) //if the win count is k or more than k, then we have got result
return best_player;
}
return best_player; //otherwise max element will be winner.
}
main() {
int arr[] = { 3, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << winner(arr, n, k);
}輸出
3
更新於: 2019年8月1日
49 次瀏覽
廣告