Javascript，在网格中找到第一个空白点

Question

我有一个网格，其中包含 x 和 y 坐标的项目。我正在尝试编写一个函数(使用 lodash)来确定第一个空白点在哪里，其中最左边的点是第一个位置。

我试图通过遍历每个点直到找到第一个空点来做到这一点。它只是一个 2 列布局，所以我以这样的模式处理它们 - x: 0, y:0 -> x:1, y:0 -> x:0, y:1 -> x:1, y :1 ... 然后一路检查所有项目以查看是否不 匹配项，这样我就知道是否有空缺。我的尝试看起来像这样:

  function fillEmptySpace(isFilled, startX, startY) {
  if (!isFilled) {
    _.forEach(items, function(item, i) {
      if (!_.isMatch(item, {
          'x': startX
        }) && !_.isMatch(item, {
          'y': startY
        })
        ) {
        console.log("empty spot at", startX, startY);
        isFilled = true;
      } else if (!_.isMatch(item, {
          'x': startX + 1
        }) && !_.isMatch(item, {
          'y': startY
        })) {
        console.log("empty spot at", startX + 1, startY);
        isFilled = true;
      }
    });

    startY += 1;
    fillEmptySpace(isFilled, startX, startY);
  }
}

fillEmptySpace(false, 0, 0);

数据看起来是这样的:

  var items = [{
  i: 'a',
  x: 0,
  y: 0,
  w: 1,
  h: 1,
  maxW: 2
}, {
  i: 'b',
  x: 1,
  y: 4,
  w: 1,
  h: 1,
  maxW: 2
}, {
  i: 'c',
  x: 0,
  y: 1,
  w: 1,
  h: 1,
  maxW: 2
}, {
  i: 'd',
  x: 0,
  y: 2,
  w: 1,
  h: 1,
  maxW: 2
}];

这是我一直在胡闹的 fiddle :https://jsfiddle.net/alexjm/ugpy13xd/38/

我似乎无法完全正确地理解这个逻辑，我不确定这一点我弄错了。任何投入将不胜感激!

请注意:根据提供的数据，它应该将第一个空白区域标识为 x:1、y:0，但是现在它说的是 0 0 处的空白点，这是不正确的。谢谢!

Answer 1

当涉及到二维数组时，可以使用x + y * width 计算一维索引。如果我们然后对 1D 索引进行排序，我们可以创建一个 O(nlogn) 解决方案:

function findEmptySpace(grid, width) {
  var index = _(grid)
    .map(function(p) { return p.x + p.y * width })
    .sortBy()
    .findIndex(_.negate(_.eq));
  if (index < 0) index = grid.length;
  return {
    x: index % width,
    y: index / width >> 0 // ">> 0" has the same result as "Math.floor"
  };
}

var items = [{x:0,y:0},{x:0,y:4},{x:0,y:1},{x:0,y:2}];

function findEmptySpace(grid, width) {
  var index = _(grid)
    .map(function(p) { return p.x + p.y * width; })
    .sortBy()
    .findIndex(_.negate(_.eq));
  if (index < 0) index = grid.length;
  return {
    x: index % width,
    y: index / width >> 0 // ">> 0" has the same result as "Math.floor"
  };
}

document.getElementById('btn').onclick = function() {
  var space = findEmptySpace(items, 2);
  items.push(space);
  console.log(space);
};

#btn { font-size: 14pt }

<script src="https://cdn.jsdelivr.net/lodash/4.13.1/lodash.min.js"></script>
<button id="btn">Fill the Empty Space</button>

如果您预先对数组进行排序，则解决方案将是最坏情况下的 O(n)。