algorithm - 在一袋弦上标记多重性

我有一个字符串包，我想映射到另一个包，这样当发现重复的字符串时，它将与该成员的多重性一起挂起，同时保留顺序。例如，给定：

["a", "b", "a", "c", "b", "a"]

我想要：

["a", "b", "a #1", "c", "b #1", "a #2"]

（由于这是部分订购的行李，[“A”，“A 1”，“A 2”，“B”，“B 1”，“C”]不是有效结果。）
一个明显的解决方案是构建多重性集（例如，{a:3，b:2，c:1}），并且在时间上是O（n），在空间上是O（n）：

function mark(names) {
    var seen = {};
    for (var i = 0; i < names.length; i++) {
        var name = names[i];
        if (name in seen) {
            names[i] = name + ' #' + seen[name];
            seen[name]++;
        } else {
            seen[name] = 1;
        }
    }

    return names;
};

我的问题是：有一个非显而易见的解决方案有更好的总体复杂性吗？或者换一种说法，当包实际上是一个集合（非常大）时，还有什么其他方法可以实现这个算法，更好地处理最坏的情况？
如果删除了poset需求，还有其他方法吗？

最佳答案

你想降低哪一个复杂度？不会有办法让时间少于o（n），因为你至少要吐出一个n长的列表，这意味着你至少要做n个操作。你也不能得到小于o（n）的总空间，因为你的输出将是n长的。
“seen”的工作空间是o（m），其中m是数组中的唯一条目数（如果使用hashmap或类似的东西）。因为m如果你在寻找节省空间的方法，并且输入是按顺序输入的，那么你可以使用o（1）个工作空间来完成这项工作，直到你看到一个新字符并重置计数器为止。同样，它不会使您的输出列表低于o（n），但这是不可能的。