题目描述

给你两个数组，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 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解题思路

1 . 将arr1分成两部分，一部分是arr2中出现的元素，一部分是为出现的元素
2. 将第一部分元素存入一个map中，值为key；第二部分元素放入一个list中
3. 将arr1中出现的arr2的元素按相对位置放入新数组
4. 对未出现的元素进行排序
5. 将排序后的元素合并至新数组

代码实现

package interview.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
public class ArrSortDemo {
	public static void main(String[] args) {
		int[] arr1={2,3,1,3,2,4,6,7,9,2,19};
		int[] arr2={2,1,4,3,9,6};
		for(int i:relativeSortArray(arr1, arr2)){
			System.out.print(i);
		}
		
	}
	 public static int[] relativeSortArray(int[] arr1, int[] arr2) {
		    HashMap<Integer, List<Integer>> map = new HashMap<>();
		        List<Integer> list = new ArrayList<>();
		        int[] res = new int[arr1.length];
		        int idx = 0;
		        //将arr2中的元素作为map的key放入
		        for (int i : arr2
		                ) {
		            map.put(i, new ArrayList<Integer>());
		        }
		        //对map赋值，值为arr2在arr1中出现的元素，list
		        for (int i :
		                arr1) {
		            if (map.containsKey(i)) {
		                map.get(i).add(i);
		            } else {
		                //arr2中没有的元素入list
		                list.add(i);
		            }
		        }
		        //先将arr1中出现的arr2的元素按相对位置放入新数组
		        for (int a : arr2
		                ) {
		            List<Integer> list1 = map.get(a);
		            for (int b : list1
		                    ) {
		                res[idx++] = b;
		            }
		        }
		        //对未出现的元素进行排序
		        Collections.sort(list);
		        
		        //将排序后的元素合并至新数组
		        for (int b : list
		                ) {
		            res[idx++] = b;
		        }
		        //新数组为所求
		        return res;
		    }
}

最后

以上就是结实万宝路为你收集整理的【LeetCode】数组的相对排序题目描述示例提示解题思路代码实现的全部内容，希望文章能够帮你解决【LeetCode】数组的相对排序题目描述示例提示解题思路代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。