设计一个算法,在已经排序的两个列表中,找出所有相同的元素
时间: 2023-05-01 21:00:56 浏览: 160
可以使用双指针的方法来解决这个问题。
首先,我们定义两个指针i和j,分别指向两个已排序的列表的起始位置。
然后,我们比较这两个位置的元素,如果它们相等,就将它们加入到结果列表中,并将两个指针都向后移动一位。
如果它们不相等,我们就将较小的那个指针向后移动一位,直到找到一个与另一个指针所指元素相等的元素,或者一个指针到达列表的末尾。
重复上述步骤,直到其中一个指针到达列表的末尾为止。
这个算法的时间复杂度是O(m+n),其中m和n分别是两个列表的长度。
相关问题
在已经排序的两个列表中,找出所有相同的元素
可以使用双指针的方法来实现。我们可以分别用两个指针 i 和 j 来遍历两个已经排好序的列表,比较两个指针指向的元素是否相等,如果相等,则将该元素加入结果列表中,并将两个指针都向后移动一位;如果不相等,则将较小的那个指针向后移动一位。直到其中一个指针遍历完整个列表为止,算法的时间复杂度为 O(n),其中 n 是两个列表的长度之和。
以下是 Python 实现代码:
```python
def find_common_elements(list1, list2):
i, j = 0, 0
common_elements = []
while i < len(list1) and j < len(list2):
if list1[i] == list2[j]:
common_elements.append(list1[i])
i += 1
j += 1
elif list1[i] < list2[j]:
i += 1
else:
j += 1
return common_elements
```
示例:
```python
list1 = [1, 3, 4, 6, 7, 9]
list2 = [1, 2, 4, 5, 9, 10]
print(find_common_elements(list1, list2)) # Output: [1, 4, 9]
```
用C++编写算法,在二叉排序树中找出任意两个不同节点的最近公共祖先
以下是用C++编写的算法,它使用了递归的方法,在二叉排序树中找出任意两个不同节点的最近公共祖先:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL; // 如果根节点为空,返回NULL
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q); // 如果根节点大于p和q的值,那么p和q在根节点的左子树中,递归左子树
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q); // 如果根节点小于p和q的值,那么p和q在根节点的右子树中,递归右子树
} else {
return root; // 如果根节点的值介于p和q的值之间,那么根节点就是它们的最近公共祖先
}
}
int main() {
TreeNode* root = new TreeNode{6, NULL, NULL};
root->left = new TreeNode{2, NULL, NULL};
root->right = new TreeNode{8, NULL, NULL};
root->left->left = new TreeNode{0, NULL, NULL};
root->left->right = new TreeNode{4, NULL, NULL};
root->left->right->left = new TreeNode{3, NULL, NULL};
root->left->right->right = new TreeNode{5, NULL, NULL};
root->right->left = new TreeNode{7, NULL, NULL};
root->right->right = new TreeNode{9, NULL, NULL};
TreeNode* p = root->left->right->left;
TreeNode* q = root->left->right->right;
TreeNode* lca = lowestCommonAncestor(root, p, q);
cout << "Lowest Common Ancestor of " << p->val << " and " << q->val << " is " << lca->val << endl;
return 0;
}
```
该程序的输出结果是:
```
Lowest Common Ancestor of 3 and 5 is 4
```
其中,root是二叉排序树的根节点,p和q是任意两个不同的节点,lca是它们的最近公共祖先。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)