前言
大家好,我是来自于华为的程序员小熊。今天给大家带来一道与数组相关的面试高频题,这道题是谷歌、腾讯、苹果和亚马逊等大厂的面试题,即力扣上的第 1122 题-数组的相对排序。
本文主要介绍计数排序+哈希表的策略来解答此题,供大家参考,希望对大家有所帮助。
数组的相对排序
给你两个数组,arr1 和 arr2,
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例及提示
解题思路
题目已提示0 <= arr1[i], arr2[i] <= 1000,由于这个范围不是很大,可以考虑不基于比较的排序-计数排序来解答。
解题步骤
1、定义一个长度为 1001 的数组 hash,用于模拟哈希表。
2、将 arr1 中的所有元素存放在 hash 数组中,其中的键为 arr1 中的元素,值为 arr1 中的元素出现的次数;
3、定义索引 i,初始化为 0,用于重置数组 arr1 中的元素值。
4、遍历数组 arr2,只要 arr2 中的元素在数组 hash 中存在,则将其赋值给 arr1,并对该元素在 hash 中出现的频次减一;
5、针对不是数组 arr2 中的元素,遍历整个数组 hash,只要其元素出现的次数在一次及以上,将其赋值给 arr1,并将该元素在 hash 中出现的频次减一。
举例
以 arr1 = [2,3,3,7,2,1], arr2 = [3,2,1] 为例子,如下图示:
示例(排序前)
按要求排序后,如下图示:
按要求排序后的 arr1
用数组 hash 记录数组 arr1 中元素出现的次数,如下图示:
遍历 arr1,将其元素出现次数记录在 hash 中
遍历数组 arr2,如下图示:
遍历 arr2
在数组 hash 中判断遍历到 arr2 中的元素出现次数是否大于 0,如下图示:
判断 hash 中 arr2 中的元素出现次数是否大于 0
更新数组 arr1 中元素的值,如下图示:
更新 arr1
完整排序过程,如下动图示:
完整排序过程
Show me the Code
C
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){
int index = 0;
int hash[1001] = {0};
for (int i = 0; i < arr1Size; ++i) {
hash[arr1[i]]++;
}
for (int i = 0; i < arr2Size; ++i) {
while (hash[arr2[i]] > 0) {
arr1[index++] = arr2[i];
hash[arr2[i]]--;
}
}
for (int i = 0; i < 1001; ++i) {
while (hash[i] > 0) {
arr1[index++] = i;
hash[i]--;
}
}
*returnSize = arr1Size;
return arr1;
}
C++
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> hash(1001);
for (int num : arr1) {
hash[num]++;
}
int i = 0;
for (int num : arr2) {
while (hash[num] > 0) {
arr1[i++] = num;
hash[num]--;
}
}
for (int num = 0; num < hash.size(); num++) {
while (hash[num] > 0) {
arr1[i++] = num;
hash[num]--;
}
}
return arr1;
}
Java
int[] relativeSortArray(int[] arr1, int[] arr2) {
int i = 0;
int [] hash = new int [1001];
for (int n : arr1) {
hash[n]++;
}
for (int n : arr2) {
while (hash[n] > 0) {
arr1[i++] = n;
hash[n]--;
}
}
for (int n = 0; n < hash.length; ++n) {
while (hash[n] > 0) {
arr1[i++] = n;
hash[n]--;
}
}
return arr1;
}
Python3
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
arr = [0 for _ in range(1001)]
ans = []
for i in range(len(arr1)):
arr[arr1[i]] += 1
for i in range(len(arr2)):
while arr[arr2[i]] > 0:
ans.append(arr2[i])
arr[arr2[i]] -= 1
for i in range(len(arr)):
while arr[i] > 0:
ans.append(i)
arr[i] -= 1
return ans
复杂度分析
时间复杂度:O(m + n),其中 m 和 n 分别为数组的长度,需要遍历一遍两个数组。
空间复杂度:O(1),额外开辟常数级别的存储空间。