Get largest value from array without sorting

I am creating a somewhat simple game, and I need 开发者_如何学Goto keep track of what players have what score. 25 people will be playing this game at one time, these players will be put into an array:

public static int[] allPlayers = new int[25];

Depending on a correct answer, the current player will earn 100 points, let's say. So, if player 1 were up, the code would be something similar to the following:

allPlayers[0] += 100;

If player 3 were up, the code on a correct answer would be:

allPlayers[2] += 100;

At the end of the game, I want to determine which player has the accumulated the most amount of points. Please note that I cannot simply sort this array because I need the order of the array to remain intact. If the order is not left intact, I will not be able to tell which player had which points to his/her name.

I'm interested to hear what you all have to say and I look forward to your responses.

Thank you very much,

Evan

No need to sort, just iterate through the array, keeping track of the largest value seen so far and the index of that value.

  var largest = -1;
  var player = -1;
  for (var i = 0; i < allPlayers.Length; ++i)
  {
       if (allPlayers[i] > largest)
       {
           player = i;
           largest = allPlayers[i];
       }
  }

  Console.WriteLine( "Player {0} wins, with score {1}", player, largest );

Handling ties is left as an exercise.

Using Linq as an alternative if you wanted a ranking of possibly more than one player (a simple loop with keeping the index of the winning player is much more effective for the base case):

var player = allPlayers.Select((x, i) => new { Score = x, Player = i })
                       .OrderByDescending(x => x.Score)
                       .First();

Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);

I'd like to be a LINQ purist and say that if you are using OrderByDescending, you're doing an O(NlogN) sort. Since max is an O(N) algorithm, we should be able to do better with LINQ. Here is my O(N) proposal for LINQ:

  var player=allPlayers.Select((x, i) => new {Score=x, Player=i})
    .Aggregate((self, next) => self.Score>=next.Score ? self : next);

  Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);

Use

int max = maxplayers.Max()//linq extension method of [] int

see this post

If you are unable to sort or keep a parallel data structure that can do the sorting or keep a a reference to the largest value, you are going to have an O(n) algorithm.

Easiest way would be to keep a reference to the highest value inserted into the array.

Using Linq:

int max = allPlayers
     .Select((x, i) = > new { Player = i, Score = x })
     .OrderByDescending(x => x.Score)
     .First();

Without Linq:

int score;
int player;

for(var i = 0; i < allPlayers.Length; i++)
{
    if(allPlayers[i] > score)
    {
        score = allPlayers[i];
        player = i;
    }
}

You can keep a tracking wich player has the max value in all the process, in each increase you can review if the new value is bigger than the old value, so in this way you can to know wich player has the max value in any moment at the game.

private int maxPlayer = 0;
private int value = 0;

public void setIncrement(int player, int amount)
{
    allPlayer[player] += amount; 
    if(allPlayer[player] > value) 
    { 
        maxPlayer = player; 
        value =  allPlayer[player];
    }
}

public int getMaxPlayer()
{
return maxPlayer;
}

Just iterate throught it once as others have suggested. That's unavoidable,

UNLESS

You wrap your players array into an array and encapsulate the way to set player score. Then you can make the comparison when adding stuff to your list.