Leetcode # 2808. Minimum Seconds to Equalize a Circular Array

https://leetcode.com/contest/biweekly-contest-110/problems/minimum-seconds-to-equalize-a-circular-array/

Solution

解這題的心路歷程

1. 找平均值 ⇒ [8,13,3,3]
2. → 找眾數.⇒ [1,11,11,11,19,12,8,7,19]
3. → 接觸到鄰居最多的數 ⇒  [8,14,10,6,7,11,12,20,7,17,10]
4. → 找最大間隔最小的數

Time Complexity: O(len(nums))
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minimumSeconds(self, nums: List[int]) -> int:
    pos = collections.defaultdict(list)
    for i, n in enumerate(nums):
      pos[n].append(i)
    min_max_gap = inf
    for n in pos:
      max_gap = -1
      if len(pos[n]) == 1:
        max_gap = len(nums) - 1
      else:
        for i in range(len(pos[n])):
          max_gap = max(max_gap, (pos[n][(i + 1) % len(pos[n])] - pos[n][i] + len(nums) - 1) % len(nums))
      min_max_gap = min(min_max_gap, max_gap)
    return ceil(min_max_gap / 2)

Last Updated on 2023/08/16 by A1go