1122. 数组的相对排序

🟢   🔖  数组 哈希表 计数排序 排序  🔗 力扣 LeetCode

题目

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

Output: [2,2,2,1,4,3,3,9,6,7,19]

Example 2:

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]

Output: [22,28,8,6,17,44]

Constraints:

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• All the elements of arr2 are distinct.
• Each arr2[i] is in arr1.

题目大意

给你两个数组，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,1,4,3,3,9,6,7,19]

示例 2:

输入： arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]

输出：[22,28,8,6,17,44]

提示：

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解题思路

思路一：哈希表

1. 统计 arr1 中元素的出现次数
   使用一个哈希表 count 来记录 arr1 中每个元素的出现次数，避免多次遍历。

2. 按照 arr2 的顺序填充结果数组
   遍历 arr2，根据其元素在 count 中的出现次数，将对应元素加入结果数组。

3. 处理未出现在 arr2 中的元素
   将 count 中剩余的元素按升序排列，并依次加入结果数组。

4. 返回结果数组
   合并两部分结果，得到最终的相对排序数组。

复杂度分析

• 时间复杂度：O(n + m + (n - m) log (n - m))，其中 m 是 arr2 的长度，n 是 arr1 的长度。
  • 构建哈希表 count，遍历 arr1，时间复杂度为 O(n)。
  • 填充结果数组时，遍历 arr2 并查找哈希表：O(m)。
  • 处理剩余元素并排序：O((n - m) log (n - m))。
  • 总时间复杂度为 O(n + m + (n - m) log (n - m))。
• 空间复杂度：O(n)， 使用了哈希表 count 和结果数组 res。

---

思路二：循环遍历

1. 遍历 arr2
   遍历 arr2 的每个元素，在 arr1 中查找与之匹配的元素，并将其加入结果数组 res 中。

   • 查找到的元素需要从 arr1 中标记为无效（可以用一个特殊值如 -1 表示）。
   • 每次找到一个匹配的元素，增加计数器 count，以记录匹配的总数量。

2. 处理剩余元素
   arr1 中剩余未标记的元素即为未出现在 arr2 中的元素。对这些元素进行排序。

3. 拼接结果
   将已排序的未匹配元素与结果数组 res 拼接，形成最终的返回结果。

复杂度分析

• 时间复杂度：O(m * n + n log n)，其中 m 是 arr2 的长度，n 是 arr1 的长度。
  • 外层循环遍历 arr2，内层循环遍历 arr1，两者形成嵌套，复杂度为 O(m * n)。
  • 剩余元素的排序，复杂度为 O(m log n)。
  • 总时间复杂度为 O(m * n + n log n)。
• 空间复杂度：O(n)，使用了结果数组 res。

代码

哈希表

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
	// 1. 统计 arr1 中每个元素的出现次数
	const count = new Map();
	for (let num of arr1) {
		count.set(num, (count.get(num) || 0) + 1);
	}

	// 2. 按照 arr2 的顺序填充结果数组
	const res = [];
	for (let num of arr2) {
		if (count.has(num)) {
			let freq = count.get(num);
			while (freq--) res.push(num);
			count.delete(num);
		}
	}

	// 3. 将剩余元素按升序加入结果数组
	const remaining = [];
	for (let [key, freq] of count.entries()) {
		while (freq--) remaining.push(key);
	}
	remaining.sort((a, b) => a - b);

	// 4. 合并结果并返回
	return res.concat(remaining);
};

循环遍历

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
	let res = [],
		count = 0; // 初始化结果数组和计数器
	for (let i = 0; i < arr2.length; i++) {
		// 遍历 arr2
		for (let j = 0; j < arr1.length; j++) {
			// 遍历 arr1
			if (arr2[i] == arr1[j]) {
				// 找到匹配元素
				res.push(arr1[j]); // 加入结果数组
				arr1[j] = -1; // 标记已处理的元素
				count++; // 更新计数器
			}
		}
	}
	arr1.sort((a, b) => a - b); // 对剩余元素排序
	return res.concat(arr1.slice(count)); // 拼接结果
};