LeetCode 字母异位词分组/数组的相对排序[哈希]-一一网

这是我参与更文挑战的第 18 天，活动详情查看：更文挑战

字母异位词分组（49）

题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例 1：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
复制代码

说明

所有输入均为小写字母。
不考虑答案输出的顺序。

思路分析

我们可以用一个哈希表进行处理，首先在获取数组中每一项的时候，先对该项进行排序，作为哈希表的 key 值，value 是一个列表，里面存放的都是未排序的项（但是每一个项排序后都等于 key 值），这样遍历整个数组，最后再将 HashMap 中的值存放到我们需要的数组中。

代码展示

解法一：时间复杂度是 ${O(n^2)}$ ，空间复杂度是 ${O(n)}$ 。

public List<List<String>> groupAnagrams(String[] strs) {
        int length = strs.length;
        Map<String,List<String>> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            char[] a = strs[i].toCharArray();
            Arrays.sort(a);
            String str = new String(a);
            if (map.containsKey(str)){
                List<String> list = map.get(str);
                list.add(strs[i]);
                map.put(str,list);
            } else {
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(str,list);
            }
        }
        List<List<String>> mList = new ArrayList<>(map.values());
        return mList;

    }
复制代码

数组的相对排序（1122）

题目描述

给你两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例 1：

输入：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]
复制代码

提示：

1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

思路分析

这道题我们也可以使用哈希表，先将数组一中的值存放到哈希表中，如果遇到key相同的，value 值自加一，再将数组二中的值存放到另一个哈希表中。

最后我们先整理 arr1 中有 arr2 的数字，将其添加到目标数组中（根据哈希表判断是否存在），最后再将剩下的 arr1 中的值放到目标数组中。

代码展示

解法一：时间复杂度是 ${O(n^2)}$ ，空间复杂度是 ${O(n)}$ 。

public static int[] relativeSortArray(int[] arr1, int[] arr2) {

//        输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]    arr2中元素各不相同  arr2 中的每个元素都出现在 arr1 中
//        输出：[2,2,2,1,4,3,3,9,6,7,19]

        int arr1Size = arr1.length;
        int arr2Size = arr2.length;

        int[] targetArray = new int[arr1Size];
        Map<Integer,Integer> arrOneMap = new HashMap<>();
        for (int i = 0; i < arr1Size; i++) {
            if (arrOneMap.containsKey(arr1[i])){
                int count = arrOneMap.get(arr1[i]);
                arrOneMap.put(arr1[i],++count);
            } else {
                arrOneMap.put(arr1[i], 1);
            }
        }

        Map<Integer,Integer> arrTwoMap = new HashMap<>();
        for (int i = 0; i < arr2Size; i++) {
            arrTwoMap.put(arr2[i],1);
        }

        //先整理 arr1 中有 arr2 的数字
        int currentIndex = 0;
        int arr2Index = 0;
        while (arr2Index < arr2Size) {
            int tempValue = arr2[arr2Index++];
            int count = arrOneMap.get(tempValue);
            for (int j = 0; j < count; j++) {
                targetArray[currentIndex++] = tempValue;
            }
        }

        //临时数组，存放不存在与arr2中的arr1的值
        int cutSize = arr1Size - currentIndex;
        int[] arr2CutArr1 = new int[cutSize];
        int cutIndex = 0;
        for (int i = 0; i < arr1Size ; i++) {
            if (!arrTwoMap.containsKey(arr1[i])){
                arr2CutArr1[cutIndex++] = arr1[i];
            }
        }
        Arrays.sort(arr2CutArr1);


        int m = 0;
        for (int i = currentIndex; i < arr1Size; i++) {
            targetArray[currentIndex++] = arr2CutArr1[m++];
        }
        return targetArray;

    }
复制代码