时间戳

首页 > 解决方案 > 所需的最少操作次数

algorithm - 所需的最少操作次数

问题描述

我在最近的采访中遇到了这个问题：

给定一个整数数组和一个整数 k。您可以对数组中的任意数量的元素执行任意次数（可能为零）的操作：

如果 number 可以被 k 整除，则将其除以 k（如果它是可整除的，则不允许将其乘以 k）

如果 number 不能被 k 整除，则将其乘以 k

您需要以这样一种方式更新此数组，即数组中的最大和最小数量之间的差异最小，并找到最小的操作数来执行此操作。

例如让 a[5] = {82, 79, 38, 49, 9} 和 k=5，我们对最后一个元素应用第二次操作。现在， a[5] = {82, 79, 38, 49, 9*5} 并且这个更新后的数组给出了最小和最大数字之间的最小差异，即 max - min = 82 - 38 = 44

我正在考虑应用递归解决方案来固定一个数字，并尝试使所有数字都尽可能接近固定数字。

但是需要更好的方法来有效地解决这个问题。提前致谢。

标签： algorithmmathdata-structures

解决方案

这在O(NlogN). 对于每个元素，我们可以写出它可以转换成的每个元素。因此，让每个元素转换为它可以成为的候选元素列表。现在问题变成了覆盖 k 个列表中的元素的最小范围，可以在O(NlogN).

解决最小范围问题的一种非常简单的方法：

  1. 将每个列表中的元素合并到一个列表中，跟踪每个元素来自的列表

  2. 在合并列表上运行一个滑动窗口，该列表具有每个子列表中的一个元素

  3. 采用候选范围

以下是我对最小范围问题的解决方案。您只需要一些样板代码即可将整数列表转换为列表列表。

from collections import deque, Counter

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:

        new = []
        # merge each list and keep track of original list
        for i in range(len(nums)):
            for j in nums[i]:
                new.append((j, i))
        # sort so each sliding window represents a range
        new.sort()

        d = deque()
        c = Counter()

        res = [-float('inf'), float('inf')]
        # iterate over sliding windows that contain each list
        for i in new:
            d.append(i)
            c[i[1]] += 1
            while len(c) == len(nums):
                res = min(res, [d[0][0], d[-1][0]], key = lambda x: x[1] - x[0])
                a, b = d.popleft()
                c[b] -= 1
                if not c[b]: del c[b]
        return res

推荐阅读