LCR 121寻找目标值

发表于2024-03-29更新于2024-03-29

LCR 121寻找目标值

我的思路

我的思路，很混乱。因为有两个方向，向下向右都增大，我就不知道该向下还是向右了。然后设计了很多情况，最后发现条件都理不顺。哭了

转变成树的思路

把数组旋转45度，他就变成了树，节点的左节点比根小，右节点比根大。问题就得到了解决

图 0

解题思路如下：

  • 确定根节点，以右上角为根节点，设置索引i=0,j=plants[0].length
  • 当 plants[i][j] > target那么找左子节点，即j--
  • 当 plants[i][j] < target那么找右子节点，即i++
  • 当 plants[i][j] = target return true
  • 若行索引或列索引越界，表示没找到目标值，返回false
  • 最后补充注意点，测试时发现有的用例是空数组，所以要在函数中判断这种情况，遇到直接return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var findTargetIn2DPlants = function (plants, target) {
  //特殊情况判断，空数组，return false
  if (plants.length === 0) return false;

  const r = plants.length;
  const c = plants[0].length;
  // 通过i,j确定根节点为右上角
  let i = 0;
  let j = c - 1;
  // 从右上角开始查找
  while (i < r && j >= 0) {
    if (plants[i][j] === target) {
      return true;
    } else if (plants[i][j] > target) {
      j--;
    } else {
      i++;
    }
  }
  return false;
};