• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= k <= n <= 30,000.
  2. 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. 1 <= k <= n <= 30,000。
  2. 所给数据范围 [-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 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap