数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告