列出出現在兩個列表中的元素？

Question

給定兩個有序數組（當然沒有重複數據），有沒有辦法找出並打印兩個數組中出現的所有元素？

我知道是否可以通過遍歷一個數組並獲取散列表，然後迭代另一個數組並查找構建的表。但是這需要O（n）的空間。

我想看看是否有這樣的方式，需要不斷額外的空間，並且只需要迭代每個數組不超過一次。可能嗎？

現在如果上述問題是可能的，如果兩個排序列表存儲在兩個二叉搜索樹中，考慮到共謀限制，是否仍然適用相同的方法？

Answer 1

對於數組，執行等效的合併操作，但沒有輸出。在合併過程中，將檢測到任何重複項。這將只涉及每個列表一個通行證，並且一旦到達任一列表的末尾就會終止。

二叉搜索樹可迭代使用堆棧遍歷，但最壞情況下的堆棧空間爲O（n）。 Morris遍歷（做網絡搜索）可以通過改變和恢復樹中的鏈接來遍歷二叉樹，而無需使用堆棧和O（n）時間複雜度（大多數節點將被訪問多次，但每個時間開銷爲倍數的n仍然是時間複雜度O（n））。典型的Morris遍歷函數在整棵樹上運行。這需要進行更改，以便每個節點依次返回，以便可以使用類似邏輯的合併來檢查重複項。我爲此寫了一些測試代碼，以便在遇到困難時提供幫助。

當按順序遍歷一個二叉樹時，每個當前節點都有一個前驅節點，一個節點按照剛好在當前節點之前的順序出現。前任節點將具有空的「右」指針。在Morris遍歷期間，每個前導節點的「右」指針從null更改爲指向它的後繼節點。最終到達前驅節點時，遵循正確的指針到達其後繼節點，然後將後繼節點的前驅節點的右指針恢復爲空。

由於已經過了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; 
} 

Answer 2

儘管有3個循環，但整體操作計數與輸入項目的數量呈線性增長。這是O（n）。儘管第一次不會像其他兩次那樣以可預測的方式增加，但它不會改變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]))

Answer 3

同時在陣列的開始

開始。

ARR [0]，ARR1 [0]

如果ARR [0]> ARR1 [0]，用於在ARR1位置等於或大於ARR1更大二進制搜索。然後你有一個相似類型的子問題arr [1..n]，arr [k..m]其中k是在二進制搜索階段找到的索引。

Answer 4

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

我試圖與通常使用二叉搜索樹實現，它的作品集。

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'; 

輸出

2 
4 

下面是問題 對於具有長度爲n的任何數組A遞歸想法，我將用A [2 .. n]至指示數組[A [2] ，...，A [n]]

設A，B爲長度爲n，m的兩個輸入數組。 如果其中任何一個都是空的，答案是微不足道的。

否則，讓我們比較第一個條目。如果A [0] == B [0]，那麼我們知道A [0]出現在兩個數組中，我們將A [0]存儲到輸出列表並繼續搜索數組A [2..n]和B [2 .. m]

如果A [0] < B [0]，那麼我們知道A {0]不會出現在這兩個數組中，因爲B中的每個元素都至少是B [0]。因此，我們繼續搜索數組A [2 .. n]和B.

類似地，如果A [0]> B [0]，我們繼續搜索數組A和B [2 .. n]

然後用遞歸可以找到答案。爲什麼它適用於二叉搜索樹？這是因爲我們只需要爲每個輸入增加一個序列。我們可以通過遍歷樹上的順序來獲得這樣的序列。