给定两个数组，arr1 和 arr2，

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：

  1. 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 
  2. 输出：[2,2,2,1,4,3,3,9,6,7,19]

提示：

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i] 各不相同

  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

    Solution

    1. /**
    2. * Note: The returned array must be malloced, assume caller calls free().
    3. */
    4. int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    5.   int book[1001] = {0};
    6.   bool vis[1001] = {false};
    7.   for(int i=0; i<arr1Size; i++) {
    8.       book[arr1[i]]++;
    9.   }
    11.   int count = 0;
    12.   for(int i=0; i<arr2Size; i++) {
    13.       int index = arr2[i];
    14.       vis[index] = true;
    15.       for(int j=book[index]; j>0; j--) {
    16.           arr1[count] = index;
    17.           count++;
    18.       }
    19.   }
    21.   for(int i=0; i<=1000; i++) {
    22.       if(!vis[i]) {
    23.           vis[i] = true;
    24.           for(int j=book[i]; j>0; j--) {
    25.               arr1[count] = i;
    26.               count++;
    27.           }
    28.       }
    29.   }
    30.   *returnSize = count;
    31.   return arr1;
    32. }

    Answer

    思路与算法

    注意到本题中元素的范围为 [0, 1000]，这个范围不是很大，我们也可以考虑不基于比较的排序，例如「计数排序」。
    具体地，我们使用一个长度为 1001（下标从 0 到 1000）的数组 frequency，记录每一个元素在数组 arr 1 中出现的次数。随后我们遍历数组arr2，当遍历到元素 x 时，我们将frequency[x]个 x 加入答案中，并将 frequency[x] 清零。（可以避免开辟新的空间用于存储是否访问过）当遍历结束后，所有在arr2中出现过的元素就已经有序了。此时还剩下没有在 arr2中出现过的元素，因此我们还需要对整个数组frequency 进行一次遍历。当遍历到元素x 时，如果frequency[x] 不为0，我们就将frequency[x] 个 x 加入答案中。

    细节

    我们可以对空间复杂度进行一个小优化。实际上，我们不需要使用长度为 1001的数组，而是可以找出数组 arr 1中的最大值 upper，使用长度为upper+1 的数组即可。

    代码

    1. int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize) {
    2.   int upper = 0;
    3.   for (int i=0; i<arr1Size; i++) {
    4.       upper = fmax(upper, arr1[i]);
    5.   }
    6.   int frequency[upper + 1];
    7.   memset(frequency, 0, sizeof(frequency));
    8.   for (int i = 0; i < arr1Size; i++) {
    9.       frequency[arr1[i]]++;
    10.   }
    11.   int* ans = malloc(sizeof(int) * arr1Size);
    12.   *returnSize = 0;
    13.   for (int i=0; i<arr2Size; i++) {
    14.       int x = arr2[i];
    15.       for (int j=0; j<frequency[x]; j++) {
    16.           ans[(*returnSize)++] = x;
    17.       }
    18.       frequency[x] = 0;
    19.   }
    20.   for (int x=0; x<=upper; x++) {
    21.       for (int i=0; i<frequency[x]; i++) {
    22.           ans[(*returnSize)++] = x;
    23.       }
    24.   }
    25.   return ans;
    26. }

    复杂度分析

  • 时间复杂度：，其中 m 和 n 分别是数组 和 的长度， 是数组 中的最大值，在本题中 不会超过 1000。遍历数组 的时间复杂度为 ，遍历数组 的时间复杂度为 ，而在遍历的过程中，我们一共需要的时间得到答案数组。

  • 空间复杂度：，即为数组 需要使用的空间。注意到与方法一不同的是，方法二的代码使用了额外的空间（而不是直接覆盖数组 ）存放答案，但我们一般不将存储返回答案的数组计入空间复杂度，并且在我们得到数组 之后，实际上也是可以将返回答案覆盖在数组