思路
只存在三种情况:相同的数是A[0]/B[0]/null。然后分别将A[0],B[0]作为target,同时遍历A和B数组。如果位置i的A和B的值与A[0],B[0]都不等,那么说明不可能完成该任务;否则相应的rotationA++或者rotationB++。最后取一个最小值(贪心)返回即可。
复杂度
时间复杂度O(n)
空间复杂度O(1)
代码
class Solution {
public int minDominoRotations(int[] A, int[] B) {
int rotation = getRotationTime(A, B, A[0]);
if (rotation != -1 || A[0] == B[0]) {
//A[0] == B[0]说明没有必要再进行后面的getRotationTime了
return rotation;
}
return getRotationTime(A, B, B[0]);
}
private int getRotationTime(int[] A, int[] B, int target) {
int rotationA = 0, rotationB = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != target && B[i] != target) {
return -1;
} else if (A[i] != target) {
rotationA++;
} else if (B[i] != target) {
rotationB++;
}
}
return Math.min(rotationA, rotationB);
}
}