时间戳

首页 > 解决方案 > 在python中计算形成GP系列的三元组的数量

python - 在python中计算形成GP系列的三元组的数量

问题描述

问题陈述是：

给定一个数组，您需要找到索引 (i,j,k) 的三元组的数量，使得这些索引处的元素对于给定的公比 r 和 i<j<k 呈几何级数。例如，arr=[1,4,16,64]。如果 r=4，我们在索引 (0,1,2) 和 (1,2,3) 处有 [1,4,16] 和 [4,16,64]。

我有一个解决方案，但我无法理解。谁能帮我吗？

def countTriplets(arr, r):
 count = 0
 
 dict = {}
 dictPairs = {}

 for i in reversed(arr):
    if i*r in dictPairs:
        count += dictPairs[i*r]
    if i*r in dict:
        dictPairs[i] = dictPairs.get(i, 0) + dict[i*r]

    dict[i] = dict.get(i, 0) + 1

 return count

标签： pythonpython-3.xfunctionloopsdictionary

解决方案

上面的程序利用两个字典来跟踪可能的三元组；

现在，从头开始（因为我们有一个给定的约束 i < j < k）

dict 跟踪元素 i，dictPairs 跟踪元素 i*r。

现在，我们检查以下内容；

  1. 如果 dictPairs 中存在元素 i*r，如果存在则存在三元组 (i, i*r, i*r*r)
  2. 如果 dict 中存在元素 i*r，如果存在则存在一对 (i, i*r)
  3. 如果它们都不存在，我们将其添加到 dict 中，使其成为未来三胞胎的候选者

始终建议跟踪算法以更好地了解它的工作原理，

假设我们有一个数组 [1,2,8,3,4,6,12] 并给定共同比率 2。

现在，从最后开始，

最初；

dict = {}
dictPairs = {}

  • 元素 12 ==> 检查 dict 或 dictPairs 中是否存在 12*2 ==> 两者都不存在 ==> 将其添加到 dict

    dict = {12 : 1} dictPairs = {}

  • 元素 6 ==> 检查 dict 或 dictPairs 中是否存在 6*2 ==> 存在于 dict ==> 将其添加到 dictPairs

    dict = {12 : 1} dictPairs = {6 : 1}

  • 元素 4 ==> 检查 dict 或 dictPairs 中是否存在 4*2 ==> 两者都不存在 ==> 将其添加到 dict

    dict = {12 : 1, 4 : 1} dictPairs = {6 : 1}

  • 元素 3 ==> 检查 dict 或 dictPairs 中是否存在 3*2 ==> 存在于 dictPairs ==> 增加计数

    dict = {12 : 1, 4 : 1} dictPairs = {6 : 1}

  • 元素 8 ==> 检查 dict 或 dictPairs 中是否存在 8*2 ==> 两者都不存在 ==> 将其添加到 dict

    dict = {12 : 1, 4 : 1, 8 : 1} dictPairs = {6 : 1}

  • 元素 2 ==> 检查 2*2 是否存在于 dict 或 dictPairs ==> 存在于 dict ==> 将其添加到 dictPairs

    dict = {12 : 1, 4 : 1, 8 : 1} dictPairs = {6 : 1, 2 : 1}

  • 元素 1 ==> 检查 dict 或 dictPairs 中是否存在 1*2 ==> 存在于 dictPairs ==> 增加计数

    dict = {12 : 1, 4 : 1, 8 : 1} dictPairs = {6 : 1, 2 : 1}

您可以看到三元组 (2, 4 , 8) 没有被选中，因为它们没有按顺序排列。

需要注意的一件事是巧妙地使用 dict.get() 函数来添加新条目。检查 dict.get() 是如何工作的

推荐阅读