LeetCode LCR 075. 数组的相对排序

Categories:

题目描述
思路分析
1. 解法一：计数排序（推荐）
2. 解法二：自定义排序
相似题目

题目描述

✅ LCR 075. 数组的相对排序

思路分析

解法一：计数排序（推荐）

核心思路：

题目值域为 0..1000，可用计数数组统计频次。

按 arr2 顺序输出对应频次元素。

剩余元素按数值从小到大输出。

复杂度分析：

时间复杂度：O(n + m)，其中 n 表示 arr1 长度，m 为值域大小。

空间复杂度：O(m)，计数数组。

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
        for (int num : arr1) {
            cnt[num]++;
        }

        int[] res = new int[arr1.length];
        int idx = 0;

        for (int num : arr2) {
            while (cnt[num] > 0) {
                res[idx++] = num;
                cnt[num]--;
            }
        }

        for (int num = 0; num < cnt.length; num++) {
            while (cnt[num] > 0) {
                res[idx++] = num;
                cnt[num]--;
            }
        }

        return res;
    }
}

func relativeSortArray(arr1 []int, arr2 []int) []int {
	cnt := make([]int, 1001)
	for _, num := range arr1 {
		cnt[num]++
	}

	res := make([]int, 0, len(arr1))

	for _, num := range arr2 {
		for cnt[num] > 0 {
			res = append(res, num)
			cnt[num]--
		}
	}

	for num := 0; num < len(cnt); num++ {
		for cnt[num] > 0 {
			res = append(res, num)
			cnt[num]--
		}
	}

	return res
}

解法二：自定义排序

核心思路：

用哈希表记录 arr2 中元素的相对顺序。

排序时优先比较顺序值，未出现过的元素按自然升序排列。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示 arr1 长度。

空间复杂度：O(n)，排序辅助空间。

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> order = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            order.put(arr2[i], i);
        }

        Integer[] nums = new Integer[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            nums[i] = arr1[i];
        }

        Arrays.sort(nums, (a, b) -> {
            int oa = order.getOrDefault(a, Integer.MAX_VALUE);
            int ob = order.getOrDefault(b, Integer.MAX_VALUE);
            if (oa != ob) {
                return oa - ob;
            }
            return a - b;
        });

        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = nums[i];
        }

        return arr1;
    }
}

import "sort"

func relativeSortArray(arr1 []int, arr2 []int) []int {
	order := map[int]int{}
	for i, num := range arr2 {
		order[num] = i
	}

	sort.Slice(arr1, func(i, j int) bool {
		oi, okI := order[arr1[i]]
		oj, okJ := order[arr1[j]]

		if okI && okJ {
			return oi < oj
		}
		if okI {
			return true
		}
		if okJ {
			return false
		}
		return arr1[i] < arr1[j]
	})

	return arr1
}

相似题目

题目	难度	考察点
791. 自定义字符串排序	中等	排序
75. 颜色分类	中等	计数/双指针
912. 排序数组	中等	排序
1331. 数组序号转换	简单	离散化
1051. 高度检查器	简单	计数排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/11913221