Re: [閒聊] 每日LeetCode

2256. Minimum Average Difference 給你一個 Integer array nums，要你找出有最小 average difference 的 index average difference 的定義為 abs(index前(含)的平均 - index後數字的平均) 其中算平均要使用整數除法 ex. nums = [2,5,3,9,5,3] index = 0 的 average difference 為 | 2/1 - (5+3+9+5+3)/5 | index = 1 的 average difference 為 | (2+5)/2 - (3+9+5+3)/4 | 如果有兩個 index 的 average difference 一樣則回傳較小的 index Example 1: Input: nums = [2,5,3,9,5,3] Output: 3 The average difference of index 3 = |(2+5+3+9)/4 - (5+3)/2| = |4-4| = 0 Example 2: Input: nums = [0] Output: 0 思路: 1.算區間總和可以先算出 prefix sum，之後能 O(1) 算出 nums[i~j] 的總和 prefix[0]=nums[0], prefix[1]=nums[0]+nums[1], prefix[2]=nums[0]+nums[1]+nums[2] 依此類推 之後如果要求 nums[i]+nums[i+1]+ ... + nums[j] 就可以直接算 prefix[j] - prefix[i-1] 2.這題的話因為是切成 nums[0:i+1] 和 nums[i+1:n] 左邊的總和就是 prefix[i] 右邊就是 prefix[n-1] - prefix[i] 之後就取平均然後相減取絕對值就好 3. Python code: class Solution: def minimumAverageDifference(self, nums: List[int]) -> int: n = len(nums) prefix = list(accumulate(nums)) diff, idx = inf, 0 for i in range(n): left = prefix[i] // (i+1) right = 0 if i == n-1 else (prefix[n-1] - prefix[i]) // (n-1-i) if abs(right - left) < diff: diff = abs(right - left) idx = i return idx 又學到一招 accumulate -- 蛤? --
※ 批踢踢實業坊(ptt.cc), 來自: 111.251.207.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670132052.A.B93.html

→ SecondRun: 我還以為你跟pandafatfat是同一個人 12/04 13:40

→ pandix: 不是== 12/04 13:43

推 SecondRun: 我之前還想說程式大師竟然是女的 結果才發現不同人 12/04 13:44