LeetCode1122.数组的相对排序（Java+计数排序）_两个正整数数组(arr1, arr2),找到一对数字,

题目

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
输入：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]

数据范围：
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000

分析

理解一下题目：arr2 中元素各不相同，arr1 中包含arr2 的所有元素
对arr1 进行排序，使arr1 中顺序跟arr2 中的相对一致；
未出现的元素升序排在末尾。
这道题没有负数，且数据范围适中，可以利用计数排序，设计一个count数组。

法一：暴力

双重循环+两个list，一个存arr2在arr1 中存在的相对次序列表，一个用于升序排序。

	public int[] relativeSortArray(int[] arr1, int[] arr2) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < arr2.length; i++) {
			for (int j = 0; j < arr1.length; j++) {
				if (arr2[i] == arr1[j]) {
					list.add(arr1[j]);
				}
			}
		}
		List<Integer> list2 = new ArrayList<>();
		for (int i = 0; i < arr1.length; i++) {
			if (!list.contains(arr1[i])) {
				list2.add(arr1[i]);
			}
		}
		Collections.sort(list2);
		list.addAll(list2);
		for (int i = 0; i < list.size(); i++) {
			arr1[i] = list.get(i);
		}
		return arr1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

法二：计数排序

计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)(其中k是整数的范围)，快于任何比较排序算法。
当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序)

计数排序可以用于：

• 利用元素的实际值来确定它们在输出数组中的位置（通过下标）
• 对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数

public int[] relativeSortArray2(int[] arr1, int[] arr2) {
		int[] count = new int[1001];// 开辟数组
		for (int i : arr1) {// 统计每个元素出现的次数
			count[i]++;
		}
		int j = 0;
		for (int i : arr2) {// 遍历arr2，改变arr1
			while (count[i] > 0) {
				arr1[j++] = i;
				count[i]--;
			}
		}
		for (int i = 0; i < count.length; i++) {
			while (count[i] > 0) {
				arr1[j++] = i;
				count[i]--;
			}
		}
		return arr1;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

参考大佬的文章

反思

自己的代码太low了，多学习吧。