动画图解一道互联网大厂的高频面试题-数组的相对排序

前言

大家好,我是来自于华为程序员小熊。今天给大家带来一道与数组相关的面试高频题,这道题是谷歌、腾讯、苹果和亚马逊等大厂的面试题,即力扣上的第 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),额外开辟常数级别的存储空间。

往期精彩回顾

哈希表妙解字母异位词

贪心让你分割更多平衡字符串---[力扣每日一题]

动画图解“两数相加”,小学生都能看懂

链表是有序的,如何快速合并呢?

上一篇:Arrays工具类的使用


下一篇:在WPF的DATAGRID中快速点击出现在ADDNEW或EDITITEM事务过程不允许DEFERREFRESH