数组A={1,2,3,4,5,6} 数组B={8,2,3,4,7,1,2,6},将数组B有序插入A中,要求合并后的数组与A,B数组顺序相同,且使尽量多的相同元素相邻排列
时间: 2023-07-16 13:17:00 浏览: 40
可以使用双指针的方法,从头开始遍历 A 和 B 数组,将 B 数组中元素插入到 A 数组中对应位置,并保持相同元素尽量相邻。
具体做法如下:
1. 初始化两个指针 i,j 分别指向 A 和 B 数组的开头。
2. 从头开始遍历 A 和 B 数组,每次比较 A[i] 和 B[j] 的大小关系:
a. 如果 A[i] < B[j],说明 B[j] 应该插入到 A[i] 的后面,因此将 B[j] 插入到 A[i+1] 的位置,并将 i 向后移动一位。
b. 如果 A[i] > B[j],说明 B[j] 应该插入到 A[i] 的前面,因此将 B[j] 插入到 A[i] 的位置,并将 i 向后移动一位。
c. 如果 A[i] == B[j],说明 B[j] 已经在 A 数组中出现过了,因此将 B[j] 插入到 A[i+1] 的位置,并将 i 向后移动一位。
3. 如果 B 数组还有剩余元素没有插入到 A 数组中,说明这些元素都比 A 数组中的元素大,因此将它们依次插入到 A 数组的末尾。
4. 最终得到的 A 数组就是合并后的数组,且满足题目要求。
以下是 Python 代码实现:
```python
def insert_sorted(A, B):
i = j = 0
while j < len(B):
if i == len(A):
A += B[j:]
break
if A[i] < B[j]:
i += 1
elif A[i] > B[j]:
A.insert(i, B[j])
j += 1
else:
A.insert(i+1, B[j])
i += 1
j += 1
return A
```
示例:
输入:A=[1,2,3,4,5,6], B=[8,2,3,4,7,1,2,6]
输出:[1, 2, 3, 4, 5, 6, 8, 7, 2, 3, 4, 1, 6]
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)