动画图解一道互联网大厂的高频面试题

程序员小熊

发布于 2021-09-29 15:46:38

4580

文章被收录于专栏：程序员小熊带你学算法程序员小熊带你学算法

前言

大家好，我是来自于华为的程序员小熊。今天给大家带来一道与数组相关的面试高频题，这道题是谷歌、腾讯、苹果和亚马逊等大厂的面试题，即数组的相对排序。

本文主要介绍计数排序+哈希表的策略来解答此题，供大家参考，希望对大家有所帮助。

数组的相对排序

给你两个数组，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

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)，额外开辟常数级别的存储空间。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-09-13，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法