数组A={1,2,3,4,5,6} 数组B={8,2,3,4,7,1,2,6},将数组B有序插入A中,要求使尽量多的相同元素相邻排列
时间: 2023-07-16 12:16:50 浏览: 78
可以使用归并排序的思想来实现这个问题。
具体步骤如下:
1. 将数组A和数组B按照从小到大的顺序合并成一个新的数组C。
2. 从数组C的第一个元素开始,依次遍历每个元素,如果该元素与前一个元素相同,则将其插入到前一个元素的后面。
3. 遍历完数组C后,就得到了一个有序的数组,其中尽量多的相同元素相邻排列。
代码实现如下:
```
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& A, vector<int>& B, vector<int>& C) {
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
C.push_back(A[i]);
i++;
} else {
C.push_back(B[j]);
j++;
}
}
while (i < A.size()) {
C.push_back(A[i]);
i++;
}
while (j < B.size()) {
C.push_back(B[j]);
j++;
}
}
void insert(vector<int>& C) {
for (int i = 1; i < C.size(); i++) {
if (C[i] == C[i-1]) {
int j = i;
while (j < C.size() && C[j] == C[i-1]) {
j++;
}
for (int k = j-1; k > i-1; k--) {
swap(C[k], C[k+1]);
}
}
}
}
int main() {
vector<int> A = {1, 2, 3, 4, 5, 6};
vector<int> B = {8, 2, 3, 4, 7, 1, 2, 6};
vector<int> C;
merge(A, B, C);
insert(C);
for (int i = 0; i < C.size(); i++) {
cout << C[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:1 1 2 2 3 4 6 6 7 8。
阅读全文