Avant toute chose, j'ai vérifié si ce type de question correspond à Stackoverflow, et en me basant sur une question similaire (javascript) et à partir de cette question: https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-sites-do- i-post-on - c'est le cas.

Alors voilà. Le défi est assez simple, à mon avis:

Étant donné cinq entiers positifs, trouvez les valeurs minimales et maximales qui peuvent être calculées en additionnant exactement quatre des cinq entiers. Imprimez ensuite les valeurs minimales et maximales respectives sur une seule ligne de deux entiers longs séparés par des espaces.

Par exemple, . Notre somme minimale est et notre somme maximale est. Nous imprimerions

16 24

Contrainte de saisie: 1 <= arr[i] <= (10^9)

Ma solution est assez simple. Voici ce que je pourrais faire de mieux:

func miniMaxSum(arr: [Int]) -> Void {
    let sorted = arr.sorted()
    let reversed = Array(sorted.reversed())
    var minSum = 0
    var maxSum = 0

    _ = sorted
        .filter({ $0 != sorted.last!})
        .map { minSum += $0 }  
    _ = reversed
        .filter({ $0 != reversed.last!})
        .map { maxSum += $0 }    

    print("\(minSum) \(maxSum)")
}

Comme vous pouvez le voir, j'ai deux tableaux triés. L'un incrémente et l'autre décrémente. Et je supprime le dernier élément des deux tableaux nouvellement triés. La façon dont je supprime le dernier élément utilise filter, ce qui crée probablement le problème. Mais à partir de là, j'ai pensé pouvoir obtenir facilement la somme minimum et maximum des 4 éléments.

J'ai passé 13 cas de test sur 14. Et ma question est: quel pourrait être le cas de test dans lequel cette solution échouera probablement?

Lien du problème: https://www.hackerrank.com/challenges/mini-max -sum / problème

2
Glenn Posadas 20 juin 2019 à 16:17

5 réponses

Meilleure réponse

Je sais que ce n'est pas codereview.stackexchange.com, mais je pense qu'un certain nettoyage est en ordre, alors je vais commencer par cela.

  1. let reversed = Array(sorted.reversed())

    L'intérêt du ReversedCollection qui est retourné par Array.reversed() est qu'il ne provoque pas de copie d'éléments, et il ne prend pas de mémoire ou de temps supplémentaire à produire. C'est simplement un wrapper autour d'une collection, et intercepte les opérations d'indexation et les modifie pour imiter un tampon qui a été inversé. Demandé .first? Il vous donnera .last de sa collection enveloppée. Demandé .last? Il retournera .first, etc.

    En initialisant un nouveau Array à partir de sorted.reversed(), vous causez une copie inutile et vaincre le point de ReversedCollection. Il y a certaines circonstances où cela peut être nécessaire (par exemple, vous voulez passer un pointeur vers un tampon d'éléments inversés à une API C), mais ce n'est pas l'un d'entre eux.

    Nous pouvons donc simplement changer cela en let reversed = sorted.reversed()

  2. -> Void ne fait rien, omettez-le.

  3. sorted.filter({ $0 != sorted.last!}) est inefficace.

    ... mais plus que cela, c'est la source de votre erreur. Il y a un bug là-dedans. Si vous avez un tableau comme [1, 1, 2, 3, 3], votre minSum sera 4 (la somme de [1, 1, 2]), alors qu'il devrait être 7 (la somme de { {X5}}). De même, le maxSum sera 8 (la somme de [2, 3, 3]) plutôt que 9 (la somme de [1, 2, 3, 3]).

    Vous effectuez une analyse de l'ensemble du tableau, en effectuant sorted.count des vérifications d'égalité, uniquement pour éliminer un élément avec une position connue (le dernier élément). À la place, utilisez dropLast(), qui renvoie une collection qui encapsule l'entrée, mais dont les opérations masquent l'existence d'un dernier élément.

    _ = sorted
        .dropLast()
        .map { minSum += $0 }      
    _ = reversed
        .dropLast()
        .map { maxSum += $0 }
    
  4. _ = someCollection.map(f)

    ... est un anti-pattern. La particularité entre map et forEach est qu'il produit un tableau résultant qui stocke les valeurs de retour de la fermeture telles qu'évaluées avec chaque élément d'entrée. Si vous n'utilisez pas le résultat, utilisez forEach

    sorted.dropLast().forEach { minSum += $0 }  
    reversed.dropLast().forEach { maxSum += $0 }  
    

    Cependant, il existe un moyen encore meilleur. Plutôt que de faire la somme en faisant muter une variable et en y ajoutant manuellement, utilisez plutôt reduce pour le faire. C'est idéal car cela vous permet de supprimer la mutabilité de minSum et maxSum.

    let minSum = sorted.dropLast().reduce(0, +)
    let maxSum = reversed.dropLast().reduce(0, +)
    
  5. Vous n'avez pas vraiment besoin de la variable reversed. Vous pouvez simplement réaliser la même chose en opérant sur sorted et en utilisant dropFirst() au lieu de dropLast():

    func miniMaxSum(arr: [Int]) {
        let sorted = arr.sorted()
    
        let minSum = sorted.dropLast().reduce(0, +)
        let maxSum = sorted.dropFirst().reduce(0, +)
    
        print("\(minSum) \(maxSum)")
    }
    
  6. Votre code suppose que la taille d'entrée est toujours 5. Il est bon de documenter cela dans le code:

    func miniMaxSum(arr: [Int]) {
        assert(arr.count == 5)
    
        let sorted = arr.sorted()
    
        let minSum = sorted.dropLast().reduce(0, +)
        let maxSum = sorted.dropFirst().reduce(0, +)
    
        print("\(minSum) \(maxSum)")
    }
    
  7. Une généralisation de votre solution utilise beaucoup de mémoire supplémentaire, dont vous ne disposez peut-être pas.

    Ce problème corrige le nombre de nombres additionnés (toujours 4) et le nombre de nombres d'entrée (toujours 5). Ce problème pourrait être généralisé à la sélection de summedElementCount nombres de n'importe quelle taille arr. Dans ce cas, le tri et la sommation deux fois sont inefficaces:

    • Votre solution a une complexité spatiale de O(arr.count)
      • Cela est dû à la nécessité de conserver le tableau trié. Si vous étiez autorisé à muter arr sur place, cela pourrait se réduire à `O (1).
    • Votre solution a une complexité temporelle de O((arr.count * log_2(arr.count)) + summedElementCount)

      • Dérivation: Trier d'abord (ce qui prend O(arr.count * log_2(arr.count))), puis additionner le premier et le dernier summedElementCount (qui est chacun O(summedElementCount))

          O (arr.count * log_2 (arr.count)) + (2 * O (summedElementCount)) = O (arr.count * log_2 (arr.count)) + O (summedElementCount) // Annihilation de la multiplication par un facteur constant = O ((arr.count * log_2 (arr.count)) + summedElementCount) // Loi d'addition pour grand O 

    Ce problème pourrait à la place être résolu avec une file d'attente de priorité limitée, comme MinMaxPriorityQueue dans la bibliothèque Gauva de Google pour Java. C'est simplement un wrapper pour tas min-max qui maintient un nombre fixe d'éléments, qui lorsqu'il est ajouté à, provoque l'expulsion du plus grand élément (selon le comparateur fourni). Si vous aviez quelque chose comme ça à votre disposition dans Swift, vous pourriez faire:

    func miniMaxSum(arr: [Int], summedElementCount: Int) {
        let minQueue = MinMaxPriorityQueue<Int>(size: summedElementCount, comparator: <)
        let maxQueue = MinMaxPriorityQueue<Int>(size: summedElementCount, comparator: >)
    
        for i in arr {
            minQueue.offer(i)
            maxQueue.offer(i)
        }
    
        let (minSum, maxSum) = (minQueue.reduce(0, +), maxQueue.reduce(0, +))
    
        print("\(minSum) \(maxSum)")
    }
    
    • Cette solution a une complexité d'espace de seulement O(summedElementCount) espace supplémentaire, nécessaire pour contenir les deux files d'attente, chacune de taille maximale summedElementCount.

      • C'est moins que la solution précédente, car summedElementCount <= arr.count
    • Cette solution a une complexité temporelle de O(arr.count * log_2(summedElementCount))

      • Derviation: la boucle for effectue arr.count itérations, chacune consistant en une opération log_2(summedElementCount) sur les deux files d'attente.

          O (arr.count) * (2 * O (log_2 (summedElementCount))) = O (arr.count) * O (log_2 (summedElementCount)) // Annihilation de la multiplication par un facteur constant = O (arr.count * log_2 (summedElementCount)) // Loi de multiplication pour gros O 
      • Je ne sais pas si c'est meilleur ou pire que O((arr.count * log_2(arr.count)) + summedElementCount). Si vous le savez, faites-le moi savoir dans les commentaires ci-dessous!

1
Alexander - Reinstate Monica 20 juin 2019 à 14:28

Ici

_ = sorted
    .filter({ $0 != sorted.last!})
    .map { minSum += $0 }  

Vous vous attendez à ce que tous les éléments, sauf le plus grand, soient ajoutés. Mais ce n'est correct que si le plus grand élément est unique. (Et de même pour la somme maximale.)

Le choix d'un tableau avec toutes les erreurs identiques rend le problème plus apparent:

miniMaxSum(arr: [1, 1, 1, 1, 1])
// 0 0 

Une solution plus simple serait de calculer la somme de tous les éléments une fois, puis d'obtenir le résultat en soustrayant le plus grand respectivement le plus petit élément du tableau. Je vous laisse la mise en œuvre :)

3
Martin R 20 juin 2019 à 13:49

Voici la solution O (n):

func miniMaxSum(arr: [Int]) {
    var smallest = Int.max
    var greatest = Int.min
    var sum = 0

    for x in arr {
        sum += x
        smallest = min(smallest, x)
        greatest = max(greatest, x)
    }

    print(sum - greatest, sum - smallest, separator: "  ")
}
3
ielyamani 20 juin 2019 à 14:29

Essayez celui-ci accepté:

func miniMaxSum(arr: [Int]) -> Void {
    let sorted = arr.sorted()
    let minSum = sorted[0...3].reduce(0, +)
    let maxSum = sorted[1...4].reduce(0, +)
    print("\(minSum) \(maxSum)"
}
1
Naser Mohamed 20 juin 2019 à 13:37

Essaye ça-

func miniMaxSum(arr: [Int]) -> Void {

var minSum = 0
var maxSum = 0
var minChecked = false
var maxChecked = false
let numMax = arr.reduce(Int.min, { max($0, $1) })
print("Max number in array: \(numMax)")

let numMin = arr.reduce(Int.max, { min($0, $1) })
print("Min number in array: \(numMin)")

for item in arr {

    if !minChecked && numMin == item {
        minChecked = true
    } else {
        maxSum = maxSum + item
    }

    if !maxChecked && numMax == item {
        maxChecked = true
    } else {
        minSum = minSum + item
    }
}
print("\(minSum) \(maxSum)")
}
0
Anupam Mishra 20 juin 2019 à 13:33