Array-Elemente wurden mit einer einzigen Bewegung um k Positionen verschoben?

Angenommen, wir haben ein Array mit n Elementen, die Reihenfolge von 1 bis n ist durcheinander. Gegeben sei eine weitere ganze Zahl K. Es stehen N Leute Schlange, um Badminton zu spielen. Die ersten beiden Spieler gehen zum Ball, dann geht der Verlierer zum Ende der Linie. Der Gewinner spielt gegen die nächste Person in der Reihe und so weiter. Sie spielen weiter, bis jemand K-mal hintereinander gewinnt. Dieser Spieler wird dann der Gewinner.

Wenn die Warteschlange [2, 1, 3, 4, 5] und K = 2 ist, ist die Ausgabe 5. Schauen Sie sich nun die Erklärung an:

(2, 1) Spiele, 2 Siege, also wird 1 zur Warteschlange hinzugefügt und die Warteschlange wird zu [3, 4, 5, 1] (2, 3) Spiele, 3 gewinnt, also werden 2 zur Warteschlange hinzugefügt und die Warteschlange wird zu [4, 5, 1, 2] (3, 4) Übereinstimmungen, 4 gewinnt, also werden 3 zur Warteschlange hinzugefügt und die Warteschlange wird zu [5, 1, 2, 3] (4, 5) Match, 5 Siege, also werden 4 zur Warteschlange hinzugefügt, die Warteschlange wird zu [1, 2, 3, 4] (5, 1) Match, 5 Siege, also werden 3 hinzugefügt zur Warteschlange. Die Warteschlange wird zu [2, 3, 4, 1]

(2, 1) Übereinstimmungen, 2 Siege, also wird 1 zur Warteschlange hinzugefügt, die Warteschlange wird zu [3, 4, 5, 1]

(2, 3) Match, 3 Siege, also werden 2 zur Warteschlange hinzugefügt, die Warteschlange wird zu [4, 5, 1, 2]

(3, 4) Match, 4 Siege, also werden 3 hinzugefügt die Warteschlange, Warteschlange wird zu [5, 1, 2, 3]

(4, 5) Rennen, 5 Siege, also werden 4 zur Warteschlange hinzugefügt, die Warteschlange wird zu [1, 2, 3, 4]

( 5, 1) Spiel, 5 Siege, also werden 3 zur Warteschlange hinzugefügt und die Warteschlange wird zu [2, 3, 4, 1]

Da 5 zwei Spiele hintereinander gewinnt, ist die Ausgabe 5. Die chinesische Übersetzung von

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

lautet:

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

Das obige ist der detaillierte Inhalt vonArray-Elemente wurden mit einer einzigen Bewegung um k Positionen verschoben?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!