[Swift]LeetCode643.子数组最大平均数I|MaximumAverageSubarrayI

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10479879.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例 1:

输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

注意:

1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。

Runtime: 1000 ms

Memory Usage: 20.1 MB

 1 class Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         var arr = nums[0..<k]
 4         var sum:Int = arr.reduce(0,+)
 5         var res:Int = sum
 6         for i in k..<nums.count
 7         {
 8             sum += nums[i] - nums[i - k]
 9             res = max(res, sum)
10         }
11         return Double(res) / Double(k)
12     }
13 }

1016ms

 1 class Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         let count = nums.count
 4         var nums = nums
 5         var maxKTotal = 0
 6         
 7         for index in 0..<count {
 8             nums[index] += index > 0 ? nums[index - 1] : 0
 9             if index + 1 == k {
10                 maxKTotal = nums[index]
11             } else if index + 1 > k {
12                 maxKTotal = max(maxKTotal, nums[index] - nums[index - k])
13             }
14         }
15         return Double(maxKTotal) / Double(k)
16     }
17 }

1148ms

 1 class Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         var maxSum = Int.min
 4         var current = 0
 5         
 6         for i in 0 ..< nums.count {
 7             if i < k {
 8                 current += nums[i]
 9             } else {
10                 maxSum = max(current, maxSum)
11                 current += nums[i] - nums[i - k]
12             }
13         }
14         maxSum = max(current, maxSum)
15         return Double(maxSum) / Double(k)
16     }
17 }

1168ms

 1 class Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         if (nums.count <= k) {
 4             return Double(nums.reduce(0,+))/Double(k)
 5         }
 6         
 7         var prev = nums[0..<k].reduce(0,+); var prevMax = prev
 8         for index in k..<nums.count {
 9             let tmp = nums[index] - nums[index-k] + prev
10             prev = tmp
11             prevMax = max(prevMax,tmp)
12         }        
13         return Double(prevMax)/Double(k)
14     }
15 }

1560ms

 1 lass Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         var i = 0
 4         var sum = 0
 5         var temp = 0
 6         for item in nums {
 7             sum += item
 8             if i < k {
 9                 temp = sum
10             } else {
11                 sum -= nums[i-k]
12                 if temp < sum {
13                     temp = sum
14                 }
15             }
16             i += 1
17         }
18         
19         return Double(temp)/Double(k)
20     }
21 }

1736ms

 1 class Solution {
 2     func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
 3         guard nums.count >= k else {
 4             return 0.0
 5         }
 6         var sum = 0
 7         var m = 0
 8         for i in 0..<k {
 9             sum += nums[i]
10         }
11         m = sum
12         for j in k..<nums.count {
13             sum -= nums[j-k]
14             sum += nums[j]
15             m = max(m, sum)
16         }
17         return Double(m)/Double(k)
18     }
19 }