在 Python 中查找给定数组中的所有良好索引

假设我们有一个数字数组 A，我们需要找到该数组的所有索引，以便在从数组中删除第 i 个元素后，数组将成为一个良好数组。我们需要记住 -

  • 良好数组是一个数组，其中一个元素等于所有其他元素的总和。
  • 这里将使用基于 1 的索引。

因此，如果输入类似于 [10, 4, 6, 2]，则输出将为 [1,4]，因为当我们删除 A[1] 时，数组将如下所示：[4, 6, 2] 并且它是良好的，因为 6 = 4+2。如果我们删除 A[4]，数组将如下所示：[10, 4, 6]，它也很好，因为 10 = 4+6。

为了解决这个问题，我们将遵循以下步骤 -

  • n := A 的大小
  • add := 0
  • my_map := 一个新的映射
  • 对于范围从 0 到 n 的 i，执行
    • my_map[A[i]] := my_map[A[i]] + 1
    • add := add + A[i]
  • 对于范围从 0 到 n 的 i，执行
    • k := add - A[i]
    • 如果 k mod 2 与 0 相同，则
      • k := k/2
      • 如果 k 在 my_map 中，则
        • 如果 (A[i] 与 k 相同且 my_map[k] > 1) 或 (A[i] 与 k 不相同)，则
          • 显示 i + 1

示例

让我们看看以下实现以更好地理解 -

现场演示

from collections import defaultdict
def find_indices(A):
   n = len(A)
   add = 0
   my_map = defaultdict(lambda:0)
   for i in range(n):
      my_map[A[i]] += 1
      add += A[i]
   for i in range(n):
      k = add - A[i]
      if k % 2 == 0:
         k = k >> 1
         if k in my_map:
            if ((A[i] == k and my_map[k] > 1) or (A[i] != k)):
               print((i + 1))
A = [10, 4, 6, 2]
find_indices(A)

输入

[10, 4, 6, 2]

输出

1
4

更新于: 2020年8月28日

474 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告