在O(n)时间内的好对数目

huangapple go评论64阅读模式
英文:

Number of Good pairs in O(n)

问题

// 能否有人解释一下for循环内部发生了什么

public int numIdenticalPairs(int[] A) {
int res = 0, count[] = new int[101];
for (int a: A) {
res += count[a]++;
}
return res;
}

英文:

// can someone please explain what's happening inside the for loop

public int numIdenticalPairs(int[] A) {
    int res = 0, count[] = new int[101];
    for (int a: A) {
        res += count[a]++;
    }
    return res;
}

答案1

得分: 1

你会迭代一个整数数组,这个数组作为生成的“count[]”中的索引。结果会将所有访问过的“count”数组中的值相加。所以,如果你的输入数组只包含唯一的数字,结果将始终为0。此外,你的输入数组不能包含超过101个唯一值,否则索引会越界。

例如:
输入数组:[0,1,2] -> 结果=0
输入数组:[1,1,2] -> 结果=1
...

在你的输入数组中,一个值出现得越频繁,对结果的影响就越大。

英文:

You iterate over an array of interger which work as your indices in the new generated count[]. The result sums up all the values in the "count" array that where visited. So if your input array has only unique numbers the result will always be 0. Also your inputArray must not contain more than 101 unique values otherwise your index is out of bounds.

e.g.
input array: [0,1,2] -> result=0
input array: [1,1,2] -> result=1
...

the more often a value is in your input-array the bigger inpact this value has on your result.

答案2

得分: 0

你使用后置递增,这意味着你将count[a]的值返回给res,然后增加该值。因此,在递增之前,res将具有count值的总和,但count中的值将增加1。

英文:

You use post increment, this mean you return the value of count[a] to res and then increment the value.
So res will have the sim of count values before the increment but the values in count will increase by 1

答案3

得分: 0

以下是翻译好的内容:

相同值之间的配对计数形成了一个数学序列。让我们将每个相同值视为节点网格中的一个节点,该节点网格包含其他每个相同值。数学计算表明,对于添加到网格的每个额外节点,它将向网格添加与网格中已有节点数量相同的配对数(因为它可以与网格中已有的每个节点配对)。

0 网格中的节点
+1 节点
配对数:0

1 网格中的节点
+1 节点
配对数:1 =(0 + 1)

2 网格中的节点
+1 节点
配对数:3 =(0 + 1 + 2)

3 网格中的节点
+1 节点
配对数:6 =(0 + 1 + 2 + 3)

依此类推。您上面的公式跟踪每个相同值的递增节点计数。然后,它还将此节点计数添加到总和 res 变量中。因此,您的循环会添加当前相同值的计数,然后增加该相同值的计数,以便在下次获得另一个相同值时继续添加。

英文:

The counting of pairs between identical values forms a mathematical series. Lets consider each identical value as a node in a node grid containing each other identical value. The math works out that for each additional node added to the grid, it will add the same number of pairs to the grid as the number of nodes already in the grid (since it can pair with every node already in the grid).

0 Node in Grid
+1 Node 
Number of Pairs: 0

1 Node in Grid
+1 Node
Number of Pairs: 1 = (0 + 1)

2 Node in Grid
+1 Node
Number of Pairs: 3 = (0 + 1 + 2)

3 Node in Grid
+1 Node
Number of Pairs: 6 = (0 + 1 + 2 + 3)

And so on. The formula you have above is keeping track of this increasing node count of each identical value. It's then also adding this node count to the total sum res variable. So your loop is adding the current count of identical values, then incrementing that count of identical values for the next time it gets another identical value.

huangapple
  • 本文由 发表于 2020年8月14日 01:48:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/63400628.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定