C++2つの秩序配列のマージ
892 ワード
剣はofferの中の思考問題を指し、秩序ある配列A、B、AはBを収容するのに十分な空間があり、A、Bを順番に並べている.
考え方:
2つのポインタで末尾から順に比較し,大きいものは新しい配列の後ろに置き,その後ポインタは順次移動する.
1.la,lbはそれぞれAとBの末尾を指し,indexは融合配列の末尾を指す
2.次に比較して、大きいのはindexで出て、indexは前に1位移動して、それから大きいlaあるいはlbは前に1位移動します
考え方:
2つのポインタで末尾から順に比較し,大きいものは新しい配列の後ろに置き,その後ポインタは順次移動する.
1.la,lbはそれぞれAとBの末尾を指し,indexは融合配列の末尾を指す
2.次に比較して、大きいのはindexで出て、indexは前に1位移動して、それから大きいlaあるいはlbは前に1位移動します
#include
using namespace std;
// ,A B, A
void MergeArr(int a[], int b[], int la, int lb)// A B
{
if (la <= 0 || lb <= 0)
return;
int index=la+lb-1;
int ida = la - 1;
int idb = lb - 1;
while (index >= 0)
{
if (a[ida] > b[idb]||idb<0) // , ,
a[index--] = a[ida--];
else if (a[ida]<=b[idb]||ida<0)
a[index--] = b[idb--];
}
}
int main()
{
int a[10] = { 3, 5, 7, 10, 15 };
int b[] = { 4, 8, 16 };
MergeArr(a, b, 5, 3);
for (int i = 0; i < 3 + 5; i++)
{
cout << a[i] << endl;
}
return 0;
}