1

我正在尝试为这个问题实现一个有效的解决方案，“假设在一个从 1 到 n 的未排序数组中，如何找到一个数字是否被删除以及如果 n 个数字被删除怎么办？”

让我说一下，我对编码没有任何问题，如果有人可以贡献我的基本想法，我就在这里。我想，将所有元素存储在哈希表中，索引是数字本身（即 hash(1)=1），然后从 1 到 n 检查哈希表是否存在值。这将花费O(n)时间。如果删除了多个数字，我当然建议这样做。对于单个值，我将计算从 1 到 n 的 nums 总和并减去数组的总和。

但是对于删除的 n 数字，我可以添加任何东西来提高效率。（如果涉及负数，尽管我的解决方案是存储（O（12）= 12 = -12），基本链接但自动将时间复杂度增加到O（2n）。这个问题实际上是我问这个问题的原因，但任何关于唯一积极因素的想法也可能有所帮助。）

4

4 回答 4

2

你的解决方案是最好的，你不能有比 O(N) 更好的复杂性（O(2N) 实际上是 O(N)）如果你有一个很好的函数来映射你的值，如果你有负数也没关系. 对于数字，我会建议一个小于 n 并且是素数的数字，我们称该数字为 P。 f(x) = x%P（对于值 x，键将是 x%P）对于 P = 9913，我们应该有： hash[10] = 10, 9923,-9903 并且所有具有（它们的值）%P 的数字都等于数组中的 10。您可以使用链表或向量来摆脱冲突。对于数字 Y，您应该将 Y 存储在索引 Y%P 中，并且在 range(1..n) 中对 i 进行一次遍历，您应该查看 i%P 位置的哈希表 for i( 基本上是 O(1 ) 查询的复杂性) 就是这样。希望它有所帮助。对不起我的英语不好 ：（

于 2012-06-11T19:04:32.517 回答
0

对于使用哈希表的解决方案，您不需要哈希表。如果您知道值是从 1 到 n，则可以使用 n 大小的布尔数组。只需遍历值数组，使用该值索引布尔数组并将该位置的值设置为 True。之后，遍历布尔数组并查找 False 值以查看已删除的值。如果您使用整数数组并在位位置设置 True/False 值，则可以使用更少的空间。这是计数排序

for i=0 to n:
    bools[values[i]] = True:
for i=0 to n:
    if(bools[i] == False):
        print("%d is missing".format(i))

如果给定负值，首先遍历数组并找到最小值。如果是 -10，则将每个值加 10，这样 -10 将转到位置 0。然后使用上述逻辑，当您找到负值时，减去 10。

“假设在一个从 1 到n的未排序数组中，如何找到一个数字是否被删除以及如果n 个数字被删除怎么办？”

如果删除了n 个数字，则数组将不包含任何值。

于 2012-06-11T01:19:00.367 回答
0

如果在扫描列表之前允许您进行一些预处理，那么您可以拥有一个预处理数据结构，该结构维护您期望拥有的数字的双向链表，并在扫描时从该链表中删除元素输入中的数字序列。双向链表中剩下的就是输入中缺少的。

对双向链表中成员的访问是 O(1)，因为列表的节点实际上是从数组创建的。从双向链表中删除是 O(1)。因此，在输入的单遍中找到丢失的数字。复杂度为 O(i+m)，其中 i 是输入的大小，m 是缺少多少个数字。

下面的代码根据输入将与之进行比较的序列的起始值和结束值创建双向链表。使用它就像：

Tracker t(0, 10);
int i;
while (std::cin >> i) t.remove(i);
t.report();

享受！

struct Node {
    static int index;
    static int stop;
    int num;
    struct Node *next;
    struct Node *prev;
    Node () : num(index++), next(0), prev(0) {
        if (index <= stop) next = this + 1;
        if (index > 0) prev = this - 1;
    }
};

struct Tracker {
    int start;
    int finish;
    Node *nodes;
    Tracker (int s, int f) : start(s), finish(f) {
        if (finish < start) throw 0;
        Node::index = start;
        Node::stop = finish + 1;
        nodes = new Node[finish - start + 2];
        nodes[finish - start + 1].next = nodes;
        nodes[0].prev = &nodes[finish - start + 1];
    }
    ~Tracker () { delete[] nodes; }
    void remove (int i) {
        Node *n = &nodes[i - start];
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void report () {
        Node *n = nodes[finish - start + 1].next;
        if (n->next == n) std::cout << "all there" << std::endl;
        else do {
            std::cout << "missing: " << n->num << std::endl;
            n = n->next;
        } while (n != &nodes[finish - start + 1]);
    }
};
于 2012-06-11T04:24:13.337 回答
0

我认为我们可以为这个问题定义多个数据结构。例如，定义 INT del = 0; 并定义一个del_list，del_list的节点可以记录地址和编号；我们有一个未排序的数组A，如果我们从这个数组A中删除一个数字，将删除的数字添加到del_list和del++中；这样我们就可以知道有多少号码被删除了，它们是什么。此外，我认为如果我们编码有更有效的方法来解决这个问题，但现在我不知道：P .. 我希望这个答案能帮助你。

于 2012-06-11T00:34:21.003 回答