Javascript��对齐并行数组的索引，避免重叠

Question

我有一个数组列表，其中相同的项目可能出现在不同的列表中（但不会出现在同一个列表中）。 我试图对这些数组进行排序，以便匹配的项目在所有数组中具有相同的索引。 我还尽量填补空缺位置，但如果某些位置保持未定义也是可以的。 用途 这是为了管理日历中每天事件的用户界面。 在我的情况下，myWrapper是一个星期，其中每个位置是一天。里面的每个数组都是当天可能发生的事件的列表。由于一个事件可能跨越多天（假设一个全天事件持续2天的简单情况），我们需要该事件出现在相同的位置，以便与前一天连续地呈现。 虽然它并不真正可见，但它成为一个占位符，前一天的块将变为两倍长。 条件

1. 所有的重复元素都是连续的，所以如果一个元素是重复的，那么在前一个数组中肯定有一份副本。
2. 每个项目在每个数组中只能出现一次（重复项只存在于不同的数组中）。
3. foo 数组的长度可能不同。
4. foo 数组始终存在，最坏情况下为空。
5. foo 数组中的顺序不重要，只要达到目标即可。
6. 包装数组不能排序。

输入

const myWrapper [
    { foo: [] },
    { foo: ['A', 'B', 'C', 'D'] },
    { foo: ['X', 'A', 'E', 'C'] },
    { foo: ['X', 'F', 'C', 'G', 'H'] },
    { foo: ['C'] }
];

期望的输出

const myWrapper [
    { foo: [] },
    { foo: ['B', 'A', 'C', 'D'] },
    { foo: ['X', 'A', 'C', 'E'] },
    { foo: ['X', 'F', 'C', 'G', 'H'] },
    { foo: [undefined, undefined, 'C'] }
];

有没有一种简洁的方法来实现这个？

我尝试了一种方法，从右边开始排序，并使用一个临时变量来交换项目。但是有时候这并不好用，因为下一个位置有时会移动前面的项目，从而干扰了上一次迭代中设置的顺序。

    let tmp;
    myWrapper.forEach((item, wrapperIndex) => {
        item.foo.forEach((currentFoo, fooIndex) => {
             // Search for match in the previous foo
             if(myWrapper[wrapperIndex - 1]) {
                const prevFoo = myWrapper[wrapperIndex - 1].foo;
                const prevIndex = prevFoo.indexOf(item);
                if (prevIndex >= 0 && prevIndex !== fooIndex) {
                    tmp = prevFoo[fooIndex];
                    prevFoo[fooIndex] = prevEvents[prevIndex];
                    prevFoo[prevIndex] = tmp;
                }
            }
        });
    });

编辑：问题还在于循环对单个项（实际上是对象，我使用字符串进行简化）进行其他操作，因此无法从右侧移动（当前项）。

输出通过Angular使用2个嵌套的*ngFor进行渲染，因此最终结果必须保持此数组结构。

- Sampgun

---

但是为什么最后没有字母 'X' 呢？第一个数组也可以是 [ 'D', 'A', 'C', 'B'] 吗？ - Isac

数组之间共享的值应该共享索引。 - pilchard

@RickardElimää 哦，好的...不，数组中的值是唯一的，因为它们实际上是带有ID的对象，所以同一个数组中不能出现两次相同的ID。 - Sampgun

输入不是缺少最后一个对象吗？ - Majed Badawi

值出现的索引在所有数组中必须相同。这是准确的约束条件吗？您想通过重新排列每个数组的元素并根据需要添加未定义元素来满足此约束条件吗？还有其他限制条件吗？ - Wyck

Answer 1

编辑

使用与我原先回答相同的重复项地图，然后使用简单的交换算法将重复值移动到其适当的索引中，是一个更简单的解决方案。

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

// find dupes and create map of indexes
let
  seen = new Set,
  dupeMap = {}, d = 0;
for (const { foo } of myWrapper) {
  for (const x of foo) {
    seen.has(x)
      ? dupeMap[x] ??= d++
      : seen.add(x);
  }
}

// swap duplicates into appropriate indexes
for (const { foo } of myWrapper) {
  let
    i, j, temp;
  for (i = 0; i < foo.length; i++) {
    j = dupeMap[foo[i]];
    if (j !== undefined && j !== i) {
      temp = foo[i];
      foo[i] = foo[j];
      foo[j] = temp;
      i--;
    }
  }
}

myWrapper.forEach(({ foo }) => console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`));

.as-console-wrapper { max-height: 100% !important; top: 0; }

---

Translated Answer

这里有一个相当简单的解决方案，避免了排序。它首先创建一个对象，该对象具有重复值的属性和该值在最终数组中的预期索引作为值。

然后，它遍历每个 foo 数组，通过重复映射中的索引将重复值放入临时数组，并将唯一值推送到第二个临时数组。

在退出之前，它尝试从唯一数组中的任何值填补临时重复数组中的空洞。

这会直接改变 myWrapper 数组。

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

// find dupes and create map of indexes
let
  seen = new Set,
  dupeMap = {}, d = 0;
for (const { foo } of myWrapper) {
  for (const x of foo) {
    seen.has(x)
      ? dupeMap[x] ??= d++
      : seen.add(x);
  }
}

for (const obj of myWrapper) {
  // collect elements into dupe/unique temp arrays
  const
    { foo } = obj,
    dTemp = [], uTemp = [];
  for (const e of foo) {
    (e in dupeMap)
      ? dTemp[dupeMap[e]] = e
      : uTemp.push(e);
  }

  // backfill empty indexes in dupe temp array
  for (const [i, d] of dTemp.entries()) {
    if (d === undefined && uTemp.length) {
      dTemp.splice(i, 1, uTemp.shift());
    }
  }

  // concat back into foo
  obj.foo = [...dTemp, ...uTemp];
}

myWrapper.forEach(({ foo }) => console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- pilchard

---

非常完美...它像魔法一样工作。我也很高兴它在可能的情况下填补了漏洞...这真是一份礼物！谢谢！ - Sampgun

我认为你应该知道这是什么意思：https://ibb.co/rFr9cnL - Sampgun

使用更简单的方法进行编辑。 - pilchard

非常好。我已经使用最新的更改更新了代码。看起来也更好！顺便说一下，由于我无法使用那些新操作符，我不得不进行一些调整...总之再次感谢！！！ - Sampgun

我进行了另一次重构，现在我有了最终的代码 :) 看看我的答案（虽然我会保留你选择的答案，因为它确实导致了解决方案！） - Sampgun

Answer 2

你的重构依赖于重复数据在数组之间的连续性，以保持一致的索引（因为它只查看一个数组后面的内容）。如果你打破这种连续性，索引就会重置。

I copied your snippet and added a 'breaking' short array.

function arrangeParallelItems(wrapper) {
  // start from the second element, so we're sure we can backlook
  wrapper.slice(1).forEach((item, itemIndex) => {
    let i = -1,
      dupeIndex,
      tmp;
    while (++i < item.foo.length) {
      if (!item.foo[i]) {
        // Skip empty values
        continue;
      }
      dupeIndex = wrapper[itemIndex].foo.indexOf(item.foo[i]);
      if (dupeIndex > -1 && dupeIndex !== i) {
        tmp = item.foo[i];
        item.foo[i] = item.foo[dupeIndex];
        item.foo[dupeIndex] = tmp;
        i--;
      }
    }
  });
}

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['H'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['F', 'C', 'G', 'H', 'X'] },
  { foo: ['C'] }
];

arrangeParallelItems(myWrapper);

myWrapper.forEach(({ foo }) =>
  console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`)
)

.as-console-wrapper { max-height: 100% !important; top: 0; }

- pilchard

---

好的，我明白你的意思了。在我的情况下，重复项总是从一个数组到另一个数组。我编辑了帖子，使所有条件更清晰。 无论如何，很高兴这种情况也被涵盖了！ - Sampgun

没问题，很高兴你已经让它在你的使用案例中工作了。 - pilchard

Answer 3

最后，我从@pilchard的工作中得出了一个更简单的解决方案。

使用简单字符串进行操作。

function arrangeParallelItems(wrapper) {
  // start from the second element, so we're sure we can backlook
  wrapper.slice(1).forEach((item, itemIndex) => {
let i = -1,
  dupeIndex,
  tmp;
while (++i < item.foo.length) {
  if (!item.foo[i]) {
    // Skip empty values
    continue;
  }
  dupeIndex = wrapper[itemIndex].foo.indexOf(item.foo[i]);
  if (dupeIndex > -1 && dupeIndex !== i) {
    tmp = item.foo[i];
    item.foo[i] = item.foo[dupeIndex];
    item.foo[dupeIndex] = tmp;
    i--;
  }
}
  });
}

const myWrapper = [
  { foo: [] },
  { foo: ['A', 'B', 'C', 'D'] },
  { foo: ['X', 'A', 'E', 'C'] },
  { foo: ['X', 'F', 'C', 'G', 'H'] },
  { foo: ['C'] }
];

arrangeParallelItems(myWrapper);

myWrapper.forEach(({ foo }) =>
console.log(`{foo: [${foo.map(e => e ?? ' ').join(', ')}]}`)
)

使用对象进行操作（这里的id是用来匹配物品的唯一键）

function arrangeParallelItems(wrapper) {
    // start from the second element, so we're sure we can backlook
    wrapper.slice(1).forEach((item, itemIndex) => {
        let i = -1, dupeIndex, tmp;
        while (++i < item.foo.length) {
            if (!item.foo[i]) {
                // Skip empty values
                continue;
            }
            dupeIndex = wrapper[itemIndex].foo.findIndex((e) => e.id === item.foo[i].id);
            if (dupeIndex > -1 && dupeIndex !== i) {
                tmp = item.foo[i];
                item.foo[i] = item.foo[dupeIndex];
                item.foo[dupeIndex] = tmp;
                i--;
            }
        }
    });
}

快速处理更多案例这里

- Sampgun

---

看起来很简洁，但如果序列中有一个最小或没有重复的数组，它就会出错。 - pilchard

为什么你这么说？我正在使用这段代码，它可以正常工作。 - Sampgun

我用许多情况进行了闪电般的测试，它运行得非常好！ - Sampgun

刚刚发布了一个简单的中断条件。 - pilchard