题解：将数组所有元素变为相同的最小操作次数

思路解析

题目要求通过不断的减法操作将数组中的所有元素变为相同。

  • 如果数组中本身只有一种元素，说明已经相同，直接返回 0；
  • 否则，目标是将数组中所有元素变为 0（任意相同值皆可，为统一处理选择 0）。

具体思路：

  1. 排序处理：

    • 将数组升序排序，便于后续查找与处理。

  2. 核心变量：

    • cur：当前已经处理的目标值，初始为 0；
    • ans：累计操作步数；
    • idx：当前正在处理的起始下标，初始化为 1（表示从第一个不同元素开始）。

  3. 差值与步数计算：

    • gap = nums[idx] - cur：表示当前目标值与待处理元素之间的差值；
    • diff = n - idx + 1：表示当前剩余的不同元素数量；
    • 利用跳步优化：steps = (gap + diff - 1) // diff，即对除法结果上取整，避免差值太大导致多余迭代，题目给出的数据范围为10**18，如果两个相邻元素为1，9999999，那么不使用跳步就会超时。

  4. 二分查找优化：

    • 使用 bisect.bisect_right(nums, cur) 快速确定当前值能影响到哪些元素，快速计算消除之后还剩下多少个不同的元素。

import bisect

class Solution(object):
    def main(self, nums):
        n = len(nums)
        if n == 1:
            return 0
        
        nums.sort()
        cur = 0
        ans = 0
        idx = 1  # 从第一个不同于最小值的元素开始处理
        
        while idx < n:
            diff = n - idx + 1       # 当前剩余未处理的元素数量
            gap = nums[idx] - cur    # 当前差值
            steps = (gap + diff - 1) // diff  # 上取整，跳步优化
            
            ans += steps
            cur += steps * diff      # 累加处理值
            
            # 二分查找：跳过所有小于等于 cur 的元素
            idx = bisect.bisect_right(nums, cur)
        
        return ans