时间戳

首页 > 解决方案 > 使数组的对和相等的最小操作数

arrays - 使数组的对和相等的最小操作数

问题描述

你会得到一个偶数长度的整数列表。考虑一个操作，您可以在 nums 中选择任意数字并使用 [1, max(nums)] 之间的值对其进行更新。返回所需的操作数，使得对于每个 i，nums[i] + nums[n - 1 - i] 等于相同的数字。这个问题可以贪婪地解决。

注意：n 是数组的大小，max(nums) 是 nums 中的最大元素。

例如：nums = [1,5,4,5,9,3] 预期的操作是 2。

解释： maxnums 是 9，所以我可以将 nums 的任何元素更改为 [1, 9] 之间的任何数字，这需要一次操作。

现在这使得 nums[0] + nums[5] = nums[1] + nums[4] = nums[2] + nums[3] = 9。我们改变了 2 个数字，它花费了我们 2 次操作，这是此输入的最小值。

我使用的方法是找到总和的中位数并用它来贪婪地找到操作的数量。让我们根据给定条件找到数组的所有和。

将这些总和存储在一个数组中并对其进行排序。sums = [4,9,14] 排序后。现在从总和中找到中位数，即 9，因为它是中间元素。

现在我使用这个中位数来平衡总和，我们可以找到操作的数量。我还添加了用于计算操作次数的代码。

int operations = 0;
for(int i=0; i<nums.size()/2; i++) {
    if(nums[i] + nums[nums.size()-1-i] == mid)
        continue;
        
    if(nums[i] + nums[nums.size()-1-i] > mid) {
        if(nums[i] + 1 <= mid || 1 + nums[nums.size()-1-i] <= mid) {
            operations++;
        } else {
            operations += 2;
        }
    } else if (maxnums + nums[nums.size()-1-i] >= mid || nums[i] + maxnums >= mid) {
        operations++;
    } else {
        operations += 2;
    }
}

此示例的总操作数为 2，这是正确的。

这里的问题是，对于某些情况，选择中位数会给出错误的结果。例如，nums = [10, 7, 2, 9, 4, 1, 7, 3, 10, 8] 需要 5 次操作，但如果选择中位数 (16)，我的代码会给出 6。

选择中位数不是最佳方法吗？任何人都可以帮助提供更好的方法吗？

标签： arraysalgorithm

解决方案

我认为以下应该有效：

  • 迭代数对
  • 对于每一对，计算该对的总和，以及通过仅更改其中一个值可以实现的最小和最大总和
  • 当开始一个需要较少更改的新“区域”时使用 -1 更新字典/地图，当该区域结束时使用 +1
  • 迭代该字典中的边界并更新所需的总更改以找到需要最少更新的总和

Python 中的示例代码，9作为您的示例的最佳总和，需要5更改。

from collections import defaultdict

nums = [10, 7, 2, 9, 4, 1, 7, 3, 10, 8]
m = max(nums)
pairs = [(nums[i], nums[-1-i]) for i in range(len(nums)//2)]
print(pairs)

score = defaultdict(int)
for a, b in map(sorted, pairs):
    low = a + 1
    high = m + b
    score[low] -= 1
    score[a+b] -= 1
    score[a+b+1] += 1
    score[high+1] += 1
print(sorted(score.items()))

cur = best = len(nums)
num = None
for i in sorted(score):
    cur += score[i]
    print(i, cur)
    if cur < best:
        best, num = cur, i
print(best, num)

总复杂度应该是 O(nlogn)，创建字典需要 O(n)，排序需要 O(nlogn)，迭代字典中的排序值需要 O(n)。（不要使用数组，否则复杂性可能会更高max(nums) >> len(nums)）

推荐阅读