Получить наибольшее значение из массива без сортировки

Question

Я создаю довольно простую игру, и мне нужно отслеживать, какие игроки имеют, какой счет. 25 человек будут играть в эту игру одновременно, эти игроки будут помещены в массив:

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

В зависимости от правильного ответа, текущий игрок, скажем, заработает 100 очков. Итак, если бы игрок 1 был в игре, код был бы примерно таким:

allPlayers[0] += 100;

Если бы игрок 3 встал, код правильного ответа был бы:

allPlayers[2] += 100;

В конце игры я хочу определить, какой игрок набрал наибольшее количество очков. Обратите внимание, что я не могу просто отсортировать этот массив, потому что мне нужен порядок массива, чтобы он оставался неизменным. Если приказ не оставлен без изменений, я не смогу определить, какой игрок имел, на что указывает его / ее имя.

Мне интересно услышать, что вы все должны сказать, и я с нетерпением жду ваших ответов.

Большое спасибо,

Evan

Answer 1

Не нужно сортировать, просто перебирайте массив, отслеживая самое большое значение, которое когда-либо было видно, и индекс этого значения.

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

Работа с галстуками оставлена ​​как упражнение.

Answer 2

Я бы хотел быть пуристом LINQ и сказать, что если вы используете OrderByDescending, вы делаете O (NlogN) сортировку. Поскольку max - это алгоритм O (N), мы должны быть в состоянии добиться большего успеха с LINQ. Вот мое предложение O (N) для 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);

Answer 3

Использование Linq в качестве альтернативы, если вы хотите получить ранжирование, возможно, более чем одного игрока (простой цикл с сохранением индекса выигравшего игрока гораздо более эффективен для базового варианта):

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

Answer 4

Использование

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

см. этот пост

Answer 5

Вы можете отслеживать, какое из игроков имеет максимальное значение во всем процессе, при каждом увеличении вы можете проверить, больше ли новое значение, чем старое, поэтому вы можете узнать, какое из игроков имеет максимальное значение.в любой момент в игре.

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

Answer 6

Использование Linq:

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

Без Linq:

int score;
int player;

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

Answer 7

Просто повторите это один раз, как предлагали другие. Это неизбежно,

UNLESS

Вы оборачиваете массив своих игроков в массив и инкапсулируете способ установить счет игрока. Затем вы можете сделать сравнение при добавлении материала в свой список.

Answer 8

Если вы не можете отсортировать или сохранить параллельную структуру данных, которая может выполнить сортировку или сохранить ссылку на наибольшее значение, у вас будет алгоритм O (n).

Самый простой способ - сохранить ссылку на самое высокое значение, вставленное в массив.