//有一批指示灯,放在正方形仪器board中测试,board[i][j]表示仪器第i行j列位置坐标上指示灯型号,现进行测试,仪器依次接收nums中数字,每接收一个数字,board中所有型号等于该数字的指示灯都会亮;当board任意一行或者任意一列被完全点亮,表示仪器测试完成,有一次交换任意两盏灯的机会,问仪器最早能在接收第几个数字时完成测试
时间: 2024-03-22 07:37:00 浏览: 51
指示灯控制,计算灯亮的个数
这是一个二分答案的问题,可以使用二分查找来解决。具体思路如下:
1. 定义左右边界left和right,分别为1和nums的长度。left表示仪器最早能在接收第1个数字时完成测试,right表示仪器最早能在接收第nums.length个数字时完成测试。
2. 在[left, right]区间内进行二分查找,假设当前查找的中间位置为mid。
3. 构造一个新的board,将mid位置的数字与任意一个不等于它的数字进行交换,并按照题目要求模拟测试过程,判断是否能在mid次接收数字后完成测试。
4. 如果能完成测试,则将right更新为mid;否则将left更新为mid+1。
5. 重复步骤2到4,直到left和right相等,此时的值即为最早能完成测试时接收的数字。
需要注意的是,为了避免重复建立board和模拟测试过程的时间复杂度,可以先使用哈希表将每种数字在board中出现的位置记录下来,并在二分查找过程中直接对哈希表进行操作。
具体实现细节可以参考下面的代码:
```java
public int earliestFinish(int[][] board, int[] nums) {
Map<Integer, List<int[]>> digitMap = new HashMap<>(); // 记录每种数字在board中出现的位置
int n = board.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int digit = board[i][j];
digitMap.computeIfAbsent(digit, k -> new ArrayList<>()).add(new int[]{i, j});
}
}
int left = 1, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
boolean finish = false;
for (int digit : digitMap.keySet()) {
if (digit == nums[mid - 1]) continue;
for (int[] pos : digitMap.get(digit)) {
int i = pos[0], j = pos[1];
int temp = board[i][j];
board[i][j] = nums[mid - 1];
if (test(board)) { // 测试board是否能在mid次接收数字后完成测试
finish = true;
break;
}
board[i][j] = temp;
}
if (finish) break;
}
if (finish) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean test(int[][] board) {
int n = board.length;
Set<Integer> rowSet = new HashSet<>(), colSet = new HashSet<>(); // 记录已经被点亮的行和列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 0) continue; // 0表示该位置上没有灯
if (rowSet.contains(i) || colSet.contains(j)) continue; // 该行或该列已经被点亮
boolean rowLight = true, colLight = true;
for (int k = 0; k < n; k++) {
if (board[i][k] != board[i][j]) rowLight = false;
if (board[k][j] != board[i][j]) colLight = false;
}
if (rowLight || colLight) {
rowSet.add(i);
colSet.add(j);
break;
}
}
}
return rowSet.size() == n || colSet.size() == n;
}
```
阅读全文