Rapide/moyen efficace d'obtenir l'indice de la valeur minimale dans la Liste des<T>?

Oui, vous pouvez supprimer la surcharge de List.IndexOf() par la construction d'une coutume Min() extension. (Vraiment, Enumerable.Min() doit avoir une extension qui permet de sélectionner l' original élément clé au lieu de sélectionner une transformation. Cette surveillance est particulièrement douloureux dans des situations de ce genre.)

public static int IndexOfMin(this IList<int> self)
{
    if (self == null) {
        throw new ArgumentNullException("self");
    }

    if (self.Count == 0) {
        throw new ArgumentException("List is empty.", "self");
    }

    int min = self[0];
    int minIndex = 0;

    for (int i = 1; i < self.Count; ++i) {
        if (self[i] < min) {
            min = self[i];
            minIndex = i;
        }
    }

    return minIndex;
}

OriginalL'auteur cdhowie

Il y a un problème avec la réponse posté par @cdhowie en ce qu'il suppose un IList<T> peut efficacement l'accès à un élément particulier par l'intermédiaire de son indexation. Alors qu'il vrai pour les tableaux et List[T], c'est à nono garantie (pour un exemple, une liste liée individuellement qui implémente Ilist<T>).

Si j'allais le faire dans un générique, Linqy façon, je ferais quelque chose comme:

public static IndexOfMinValue<T>( this IList<T> list ) where T:IComparable
{
  if ( list == null ) throw new ArgumentNullException("list") ;
  int? offset = null ;
  T    min    = default(T) ;

  int i = 0 ;
  foreach ( T item in list )
  {
    if ( !offset.HasValue || item.CompareTo(min) < 0 )
    {
       offset = i ;
       min    = item ;
    }
    ++i ;
  }

  if ( !offset.HasValue ) throw new ArgumentOutOfRangeException("list","list is empty") ;
  return offset.Value ;
}

Ou, sans doute plus propre, puisque nous débarrasser du superflu et de l'initialisation et étrangère comparer dans le corps de la boucle:

public static int IndexOfMin<T>( this IList<T> list ) where T:IComparable
{
  if ( list == null ) throw new ArgumentNullException("list") ;

  IEnumerator<T> enumerator  = list.GetEnumerator() ;
  bool           isEmptyList = ! enumerator.MoveNext() ;

  if ( isEmptyList ) throw new ArgumentOutOfRangeException("list","list is empty") ;

  int minOffset = 0 ;
  T   minValue  = enumerator.Current ;
  for ( int i = 1 ; enumerator.MoveNext() ; ++i )
  {
    if ( enumerator.Current.CompareTo(minValue) >= 0 ) continue ;
    minValue  = enumerator.Current ;
    minOffset = i ;
  }

  return minOffset ;
}

Vous pouvez également utiliser le stock de Linq Aggregate() surcharge, si c'est pas plus propre ou plus simple que la force brute de la méthode (probablement moins efficace, trop, à mon humble avis):

IList<int> = GetSomeIntegers() ;

int minIndex = list.Aggregate( (Tuple<int,int,int>)null,
  ( acc , item ) => {
    int offset     = 0    ;
    int minValue   = item ;
    int minOffset  = 0    ;
    if ( acc != null )
    {
      offset    = acc.Item3 + 1 ;
      minValue  = item < acc.Item1 ? item   : acc.Item1 ;
      minOffset = item < acc.Item1 ? offset : acc.Item2 ;
    }
    return new Tuple<int, int, int>( minValue , minOffset , offset ) ;
  }).Item2 ;

OriginalL'auteur Nicholas Carey

J'ai amélioré @cdhowie de réponse un peu pour le rendre plus puissant. Si il y a plus d'un minimum d'éléments, alors cette méthode retourne la première.

public static T GetMin<T, TOrder>(this IEnumerable<T> self, Func<T, TOrder> orderFunc, 
                                  out int minIndex, IComparer<TOrder> cmp = null)
{
    if (self == null) throw new ArgumentNullException("self");            

    IEnumerator<T> selfEnumerator = self.GetEnumerator();
    if (!selfEnumerator.MoveNext()) throw new ArgumentException("List is empty.", "self");

    if (cmp == null) cmp = Comparer<TOrder>.Default;

    T min = selfEnumerator.Current;
    minIndex = 0;
    int intCount = 1;
    while (selfEnumerator.MoveNext ())
    {
        if (cmp.Compare(orderFunc(selfEnumerator.Current), orderFunc(min)) < 0)
        {
            min = selfEnumerator.Current;
            minIndex = intCount;
        }
        intCount++;
    }

    return min;
}

OriginalL'auteur pengdlzn

Min de Calcul: Trouver le Min valeur dans une collection ne peut pas être fait plus vite que O(n) donc c'est peut-être pas de meilleur moyen que de cela, mais juste une autre dans le style de code.

Trouver Étape: en fonction de votre problème, vous pouvez utiliser certains de structure de données (telles que l'arbre binaire, tas d'arbre, ...) de sorte que vous pouvez trouver l'index de plus en plus vite.

En utilisant quelque chose comme min-segment de l'arbre, vous pouvez obtenir la valeur min avec O(1) en charge de spécial à Ajouter, Supprimer des fonctions.

OriginalL'auteur Hossein Narimani Rad