列出两个列表中出现的元素？

Given two sorted arrays(without duplicates of course), is there a way to find out and print all the elements that appeared in both arrays?

给定两个排序的数组(当然没有重复),有没有办法找出并打印出两个数组中出现的所有元素?

I know if could get by iterating through one array and build a hashtable, and then iterate the other array and lookup the built table. But that would requires a space of O(n).

我知道是否可以通过迭代一个数组并构建一个哈希表,然后迭代另一个数组并查找构建的表。但这需要一个O(n)的空间。

I'm trying to see if there is such a way that requires constant additional space, and only requires iterating of each array no more than once. Is it possible?

我试图看看是否存在需要不断增加空间的方式,并且只需要对每个数组进行迭代不超过一次。可能吗?

Now if the above question is possible, if the two sorted list are stored in two binary search trees, is the same approach still applicable given the complicity restriction?

现在,如果上述问题是可能的,如果两个排序列表存储在两个二叉搜索树中,那么同样的方法是否仍然适用于共犯限制?

4 个解决方案

#1

For arrays, do the equivalent of a merge operation, but with no output. During the merge process, any duplicates will be detected. This will involve only one pass per list, and will terminate as soon as the end of either list is reached.

对于数组,执行等效的合并操作,但没有输出。在合并过程中,将检测到任何重复项。这将只涉及每个列表一次传递,并且一旦到达任一列表的末尾就会终止。

A binary search tree can be traversed iteratively using a stack, but the worst case stack space is O(n). A Morris traversal (do a web search) can traverse a binary tree without using a stack and with O(n) time complexity by changing and restoring the links in the tree (most nodes will be visited multiple times each, but time overhead of multiples of n is still time complexity O(n)). A typical Morris traversal function operates on an entire tree. This will need to be changed so that it returns with each node in order so that merge like logic can be used to check for duplicates. I wrote some test code for this so I can help in case you get stuck.

可以使用堆栈迭代地遍历二进制搜索树,但最坏情况的堆栈空间是O(n)。 Morris遍历(执行Web搜索)可以在不使用堆栈的情况下遍历二叉树,并通过更改和恢复树中的链接来实现O(n)时间复杂度(大多数节点将被访问多次,但是时间开销为多次n仍然是时间复杂度O(n))。典型的Morris遍历功能在整棵树上运行。这将需要更改,以便它按顺序返回每个节点,以便可以使用类似逻辑的合并来检查重复项。我为此写了一些测试代码,以便在遇到问题时我可以提供帮助。

When traversing a binary tree in order, each current node has a predecessor node, a node that occurs in order just before the current node. The predecessor node will have a null "right" pointer. During a Morris traversal, each predecessor node's "right" pointer is changed from null to point to it's successor node. Eventually when a predecessor node is reached, it's right pointer is followed to reach its successor node, and then the successor node's predecessor node's right pointer is restored back to null.

当按顺序遍历二叉树时,每个当前节点都有一个前驱节点,即在当前节点之前按顺序发生的节点。前任节点将具有空“右”指针。在Morris遍历期间,每个前任节点的“右”指针从null更改为指向其后继节点。最终,当到达前驱节点时,遵循右指针到达其后继节点,然后后继节点的前任节点的右指针恢复为空。

Since it's been 2 days, here is example code for a Morris traversal function that returns with a pointer to each node. Part of the logic is in main()'s for loop that advances the returned pointer to the right before calling the traversal function again (an alternative would be to have a helper function that advances to the right and then calls the main traversal function):

由于它是2天,这里是一个Morris遍历函数的示例代码,它返回一个指向每个节点的指针。部分逻辑在main()的for循环中,在再次调用遍历函数之前将返回的指针前进到右边(另一种方法是让一个辅助函数向右前进,然后调用主遍历函数) :

#include<stdio.h>
#include<stdlib.h>

/* binary tree node */
typedef struct BTNODE_
{
    struct BTNODE_* left;
    struct BTNODE_* right;
    int data;
}BTNODE;

/* traverse binary tree without stack */
/* initial input parameter is pointer to root */
/* predecessor of cur is largest value < cur */
/* predecessor of cur = cur->left->right->right->right ... */
BTNODE * MorrisTraversal(BTNODE *cur)
{
BTNODE *pre;
    if(cur == NULL)
        return(NULL);
    while(cur != NULL){
        /* if left end of branch, return */
        if(cur->left == NULL)
            return(cur);
        /* advance pre to predecessor of cur */
        pre = cur->left;
        while(pre->right != NULL && pre->right != cur)
            pre = pre->right;
        /* if right end of branch, change pre->right = cur */
        /*  and advance cur left */
        if(pre->right == NULL){
            pre->right = cur;
            cur = cur->left;
        /* else back at cur, so restore pre->right = NULL */
        /*  and return */
        } else {
            pre->right = NULL;
            return(cur);
        }
    }
    return(NULL);
}

BTNODE* newbtNode(int data)
{
BTNODE* btNode = (BTNODE*) malloc(sizeof(BTNODE));
    btNode->left = NULL;
    btNode->right = NULL;
    btNode->data = data;
    return(btNode);
}

int main()
{
BTNODE *cur;
/* create a 15 element binary tree */
BTNODE *root = newbtNode(8);
    root->left                = newbtNode( 4);
    root->left->left          = newbtNode( 2);
    root->left->left->left    = newbtNode( 1);
    root->left->left->right   = newbtNode( 3);
    root->left->right         = newbtNode( 6);
    root->left->right->left   = newbtNode( 5);
    root->left->right->right  = newbtNode( 7);
    root->right               = newbtNode(12);
    root->right->left         = newbtNode(10);
    root->right->left->left   = newbtNode( 9);
    root->right->left->right  = newbtNode(11);
    root->right->right        = newbtNode(14);
    root->right->right->left  = newbtNode(13);
    root->right->right->right = newbtNode(15);
    for(cur = root; cur; cur = cur->right){
        cur = MorrisTraversal(cur);
        printf("%2d ", cur->data);
    }
    return 0;
}

#2

Start at beginning of both the arrays.

从两个数组的开头开始。

arr[0], arr1[0]

If arr[0] > arr1[0], binary search for position in arr1 that is equal to or greater than arr1. Then you have a sub problem of similar type arr[1..n], arr[k..m] where k is the index that was found in the binary search phase.

如果arr [0]> arr1 [0],二进制搜索arr1中等于或大于arr1的位置。然后你有一个类似类型的子问题arr [1..n],arr [k..m]其中k是在二进制搜索阶段找到的索引。

#3

Even though there are 3 loops the overall operation count grows linearly with the number of input items. This is O(n). While the first while doesn't increment in a predictable way like the other two, it does not change O(n). This is basically a merge operation. During the merge process, any duplicates will be detected. This will involve only one pass per list, and will terminate as soon as the end of either list is reached.

即使有3个循环,整个操作计数也会随着输入项的数量线性增长。这是O(n)。虽然第一个while不像其他两个那样以可预测的方式递增,但它不会改变O(n)。这基本上是一个合并操作。在合并过程中,将检测到任何重复项。这将只涉及每个列表一次传递,并且一旦到达任一列表的末尾就会终止。

function mergetwosorted(a, b) {

  var c = new Array(a.length + b.length),
    ai = 0,
    bi = 0,
    ci = 0;


  while (ai < a.length && bi < b.length) {

    if (a[ai] < b[bi]) {
      c[ci] = a[ai];
      ai++;
    } else {
      c[ci] = b[bi]
      bi++;
    }
    ci++;
  }

  while (ai < a.length) {
    c[ci] = a[ai];
    ai++
    ci++
  }
  while (bi < b.length) {
    c[ci] = b[bi];
    ci++;
    bi++;
  }
  return c;

}


console.log(mergetwosorted([1, 2, 3, 4], [2, 3, 4, 5, 6]))

#4

I think you can take a look at std::set_difference http://en.cppreference.com/w/cpp/algorithm/set_intersection

我想你可以看看std :: set_difference http://en.cppreference.com/w/cpp/algorithm/set_intersection

I tried with set which is usually implemented using binary search tree and it works.

我尝试使用通常使用二叉搜索树实现的set,它可以工作。

set<int> s1 = {1, 2, 4, 5};
set<int> s2 = {0, 2, 4, 7};
vector<int> v;
set_intersection(s1.begin(), s1.end(),
                 s2.begin(), s2.end(),
                 back_inserter(v));
for (auto i : v)
    cout << i << '\n';

Output

2
4

Here is a recursive idea for the problem For any array A with length n, I will use A[2 .. n] to indicate array [A[2], ..., A[n]]

这是问题的递归思路对于长度为n的任何数组A,我将使用A [2 .. n]来表示数组[A [2],...,A [n]]

Let A, B be the two input arrays with length n, m. If either is empty, the answer is trivial.

设A,B为长度为n,m的两个输入数组。如果其中任何一个是空的,答案是微不足道的。

Otherwise, lets compare the first entry.

否则,让我们比较第一个条目。

If A[0] == B[0], then we know A[0] appear in both array, we store A[0] to output list and continue our search for arrays A[2 .. n] and B[2 .. m]

如果A [0] == B [0],那么我们知道A [0]出现在两个数组中,我们将A [0]存储到输出列表并继续搜索数组A [2 .. n]和B [2] ..米]

If A[0] < B[0], then we know A{0] will not appear in both array as every elements in B is at least B[0]. So we continue our search for arrays A[2 .. n] and B.

如果A [0]

Similarly if A[0] > B[0], we continue our search for arrays A and B[2 .. n]

类似地,如果A [0]> B [0],我们继续搜索数组A和B [2 .. n]

Then with recursion you can find the answer. And why does it works for binary search tree? It is because we only need an increasing sequence for each input. And we can get such sequence by in order traversal on the tree.

然后通过递归你可以找到答案。为什么它适用于二叉搜索树?这是因为我们只需要为每个输入增加序列。我们可以通过在树上遍历顺序来获得这样的序列。