题目描述
给你两个数组，arr1和arr2，
arr2中的元素各不相同
arr2中的每个元素都出现在arr1中
对arr1中的元素进行排序，使arr1中项的相对顺序和arr2中的相对顺序相。未在arr2中出现的元素需要按照升序放在arr1的末尾。
示例
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19]，arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示
arr1.length , arr2.length <= 1000
0 <= arr1[ i ] , arr2[ i ] <= 1000
arr2中的元素arr2[ i ]各不相同
arr2中的每个元素arr2[ i ]都出现在arr1中
题解
解题思路蛮简单的，按照顺序取arr2中的元素，遍历arr1找到相同的元素，依次换到arr1的前面。arr2遍历结束后，arr1前面的元素就都按照arr2中的顺序排好了，接下来把arr1中剩下的元素（也就是arr2中没出现的元素）按升序排序。排序方法可以是冒泡排序，插入排序等等。我采用的使插入排序。
代码如下：
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
int index_arr1, index_arr2, i, j;
int flag,temp;
for(index_arr2 = 0, index_arr1 = 0; index_arr2 < arr2.size(); index_arr2++)
{
flag = arr2[index_arr2];
for(i = index_arr1; i < arr1.size(); i++)
{
if(arr1[i] == flag)
{
temp = arr1[index_arr1];
arr1[index_arr1] = arr1[i];
arr1[i] = temp;
index_arr1++;
}
}
}
for(i = index_arr1+1; i < arr1.size(); i++)
{
if(arr1[i-1] > arr1[i])
{
temp = arr1[i];
for(j = i-1; arr1[j] > temp && j >= index_arr1 ; j--)
{
arr1[j+1] = arr1[j];
}
arr1[j+1] = temp;
}
}
return arr1;
}
结果
虽然简单，但我还是提交了3次，挺菜的【捂脸
问题主要出在后半部分——插入排序
而且问题都是出在这个循环判断条件：
for(j = i-1; arr1[j] > temp && j >= index_arr1 ; j--)
——————第1次提交的代码——————
temp = arr1[i-1];
for(j = i-1; j > index_arr1-1; j--)
我可能是个智障吧【苦笑】，首先temp应该赋值arr1[ i ]，arr1[ i ]才是要插入的元素，我也不知道我当时是怎么想的。其次，循环结束条件应该是找到找到比待插入元素小的元素下标，应该是元素和元素的比较而不是下标和下标的比较，所以判断条件应该是 arr1[ j ] > temp。
——————第2次提交的代码——————
for(j = i-1; arr1[ j ] > temp; j--)
纠正了第1次的错误，样例测试数据也通过了。然而提交结果告诉我下标越界，呵呵……
不通过的测试数据为：arr1 = [26,21,11,20,50,34,1,18]，arr2 = [21,11,26,20]
如果按照这次的代码执行的话，当temp = 1时，j会一直自减，当j减小到-1时，下标就越界啦~
所以应该再加上一个判断条件，即：j >= index_arr1，就是说j减小到index_arr1的前一位就不要再减小啦，因为index_arr1之前的元素都是排好的，不能再改变了。
最后po以下结果~~~速度还算可以吧
