1128. 等价多米诺骨牌对的数量

题目链接1128. 等价多米诺骨牌对的数量 - 力扣LeetCode题目描述给你一组多米诺骨牌dominoes。形式上dominoes[i] [a, b]与dominoes[j] [c, d]等价 当且仅当 (a c且b d) 或者 (a d且b c) 。即一张骨牌可以通过旋转0度或180度得到另一张多米诺骨牌。在0 i j dominoes.length的前提下找出满足dominoes[i]和dominoes[j]等价的骨牌对(i, j)的数量。题目示例示例 1 :输入dominoes [[1,2],[2,1],[3,4],[5,6]] 输出1示例 2 :输入dominoes [[1,2],[1,2],[1,1],[1,2],[2,2]] 输出3解题思路问题理解给定一组多米诺骨牌每个骨牌由两个数字表示如[a, b]。两个骨牌[a, b]和[c, d]是等价的如果a c b d或a d b c。需要统计所有等价骨牌对的数量。关键思路将每个骨牌标准化为[min(a, b), max(a, b)]这样可以统一等价骨牌的表示形式。使用一个二维数组cnt来统计每种标准化骨牌的出现次数。对于每个骨牌其等价对的数量就是之前已经出现的相同标准化骨牌的数量。优化点标准化处理避免了重复比较直接通过计数数组快速查询和更新。时间复杂度为O(n)空间复杂度为O(1)因为cnt的大小固定为10x10。题解代码classSolution{publicintnumEquivDominoPairs(int[][]dominoes){intans0;// 初始化等价骨牌对的数量int[][]cntnewint[10][10];// 创建一个10x10的计数数组用于统计每种骨牌的出现次数for(int[]d:dominoes){// 遍历每个骨牌intaMath.min(d[0],d[1]);// 获取骨牌中的较小值intbMath.max(d[0],d[1]);// 获取骨牌中的较大值保证a banscnt[a][b];// 将当前骨牌的计数加到ans中并更新计数}returnans;// 返回等价骨牌对的总数}}复杂度分析时间复杂度遍历所有骨牌需要O(n)时间其中n是骨牌的数量。每个骨牌的处理标准化和计数更新是O(1)操作。总时间复杂度为O(n)。空间复杂度使用了一个固定大小的二维数组cnt大小为10x10因此空间复杂度为O(1)。