Swift Mini-Max Sum One 测试用例失败 - HackerRank

Question

首先，我检查了这种问题是否适合Stackoverflow，并基于一个类似的问题(javascript)和这个问题：https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-sites-do-i-post-on - 它确实如此。

所以它来了。在我看来，挑战非常简单：

给定五个正整数，找到最小值和最大值 可以通过对五个整数中的四个进行求和来计算。然后 将相应的最小值和最大值打印为单行 两个空格分隔的长整数。

例如。我们的最小总和是，我们的最大总和是。我们会 打印

16 24

输入约束：1 <= arr[i] <= (10^9)

我的解决方案非常简单。这是我最擅长的：

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)")
}

如您所见，我有两个排序数组。一个是递增，另一个是递减。我正在删除两个新排序数组的最后一个元素。我删除最后一个元素的方法是使用filter，这可能会产生问题。但是从那里，我认为我可以很容易地得到 4 个元素的最小和最大总和。

我通过了 13/14 个测试用例。我的问题是，这个解决方案可能会失败的测试案例是什么？

问题链接：https://www.hackerrank.com/challenges/mini-max-sum/problem

Answer 1

这里

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

您的期望是添加除最大元素之外的所有元素。但这是正确的，最大的元素是唯一的。 (同样，对于最大总和。

选择具有所有相同错误的数组会使问题更加明显：

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

更简单的解决方案是计算一次所有元素的总和，然后通过减去最大和最小的数组元素来得到结果。我会把实现留给你:)

Answer 2

这是 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: "  ")
}

Answer 3

我知道这不是 codereview.stackexchange.com，但我认为需要进行一些清理，所以我将从这个开始。

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

   Array.reversed()返回的ReversedCollection的全部意义在于它不会导致元素的副本，并且不会占用任何额外的内存或时间来生成。它只是集合的包装器，截获索引操作并更改它们以模拟已反转的缓冲区。问.first？它会给你.last它的包装收藏。要求.last？它会返回.first，等等。

   通过从sorted.reversed()初始化新Array，您会导致不必要的副本，并破坏ReversedCollection点。在某些情况下，这可能是必要的(例如，您希望将指向反向元素缓冲区的指针传递给 C API)，但这不是其中之一。

   因此，我们可以将其更改为let reversed = sorted.reversed()

2. -> Void什么都不做，省略它。

3. sorted.filter({ $0 != sorted.last!})效率低下。

   。但更重要的是，这是您错误的根源。这其中有一个错误。如果你有一个像[1, 1, 2, 3, 3]这样的数组，你的minSum将是4([1, 1, 2]之和)，而它应该是7([1, 1, 2, 3]的总和)。类似地，maxSum将是8([2, 3, 3]的 sume)而不是9([1, 2, 3, 3]的总和)。

   您正在扫描整个数组，执行sorted.count相等性检查，只是丢弃具有已知位置的元素(最后一个元素)。请改用dropLast()，它将返回一个包装输入的集合，但其操作会屏蔽最后一个元素的现有元素。

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

4. _ = someCollection.map(f)

   。是一种反模式。map和forEach之间的区别在于，它生成一个结果数组，该数组存储使用每个输入元素评估的闭包的返回值。如果不打算使用结果，请使用forEach

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

   但是，还有更好的方法。与其通过改变变量并手动添加变量来求和，不如使用reduce来执行此操作。这是理想的，因为它允许您 消除minSum和maxSum的可变性 .

   let minSum = sorted.dropLast().reduce(0, +)
   let maxSum = reversed.dropLast().reduce(0, +)
   

5. 您根本不需要reversed变量。您可以通过在sorted上运行并使用dropFirst()而不是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. 代码假定输入大小始终为 5。最好在代码中记录这一点：

   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. 解决方案的通用化会使用大量额外的内存，而这些内存可能不可用。

   此问题修复了求和数字的数量(始终为 4)和输入数字的数量(始终为 5)。这个问题可以推广到从任何大小arr中挑选summedElementCount数字。在这种情况下，两次排序和求和效率低下：

   • 解决方案的空间复杂度为O(arr.count)
     • 这是由于需要保存排序的数组引起的。如果允许您就地改变arr，这可能会减少到'O(1)。

   • 您的解决方案具有O((arr.count * log_2(arr.count)) + summedElementCount)的时间复杂度

     • 推导：首先排序(需要O(arr.count * log_2(arr.count)))，然后对第一个和最后一个summedElementCount求和(即每个O(summedElementCount))

       O(arr.count * log_2(arr.count)) + (2 * O(summedElementCount))
       = O(arr.count * log_2(arr.count)) + O(summedElementCount) // Annihilation of multiplication by a constant factor
       = O((arr.count * log_2(arr.count)) + summedElementCount) // Addition law for big O
       

   这个问题可以通过有界优先级队列来解决，就像谷歌Java的Gauva库中的MinMaxPriorityQueue一样。它只是最小-最大堆的包装器，它维护固定数量的元素，当添加到时，会导致最大的元素(根据提供的比较器)被逐出。如果你在 Swift 中有这样的东西，你可以做：

   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)")
   }
   

   • 此解决方案的空间复杂性仅为O(summedElementCount)个额外空间，需要容纳两个队列，每个队列的最大大小为summedElementCount。

     • 这比以前的解决方案要少，因为summedElementCount <= arr.count

   • 此解决方案的时间复杂度为O(arr.count * log_2(summedElementCount))

     • 派生：for 循环执行arr.count迭代，每次迭代都由两个队列上的log_2(summedElementCount)操作组成。

       O(arr.count) * (2 * O(log_2(summedElementCount)))
       = O(arr.count) * O(log_2(summedElementCount)) // Annihilation of multiplication by a constant factor
       = O(arr.count * log_2(summedElementCount)) // Multiplication law for big O
       

     • 我不清楚这比O((arr.count * log_2(arr.count)) + summedElementCount)更好还是更差.如果您知道，请在下面的评论中告诉我！

Answer 4

试试这个接受：

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)"
}

Answer 5

试试这个-

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)")
}

Answer 6

试试这个：

func miniMaxSum(arr: [Int]) -> Void {
let min = arr.min()
let max = arr.max()
let total = arr.reduce(0, +)
print(total - max!, total - min!, separator: " ")
}