Array elements moved k positions by a single move?

Suppose we have an array containing n elements, the order from 1 to n is scrambled. Given another integer K. There are N people lining up to play badminton. The first two players will go to the ball, then the loser will go to the end of the line. The winner will play the next person in line and so on. They will keep playing until someone wins K times in a row. That player then becomes the winner.

If the queue is [2, 1, 3, 4, 5] and K = 2, then the output will be 5. Now look at the explanation:

(2, 1) matches, 2 wins, so 1 will be added to the queue and the queue becomes [3, 4, 5, 1] ​​(2, 3) matches, 3 wins, so 2 will be added to the queue, the queue becomes [4, 5, 1, 2] (3, 4) matches, 4 wins, so 3 will be added to the queue, the queue becomes [5, 1, 2, 3] (4, 5) matches, 5 wins, so 4 will be added to the queue, the queue becomes [1, 2, 3, 4] (5, 1) matches, 5 wins, so 3 will be added to the queue, the queue becomes [2, 3, 4, 1]

(2, 1) matches, 2 wins, so 1 will be added to the queue, the queue becomes [3, 4, 5 , 1]

(2, 3) matches, 3 wins, so 2 will be added to the queue, and the queue becomes [4, 5, 1, 2]

(3, 4 ) match, 4 wins, so 3 will be added to the queue, the queue becomes [5, 1, 2, 3]

(4, 5) match, 5 wins, so 4 will be added to the queue , the queue becomes [1, 2, 3, 4]

(5, 1) matches, 5 wins, so 3 will be added to the queue, the queue becomes [2, 3, 4, 1 ]

Since 5 won two games in a row, the output is 5.

Algorithm

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

Example

Example

#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);
}

Output

3

The above is the detailed content of Array elements moved k positions by a single move?. For more information, please follow other related articles on the PHP Chinese website!