This is the 18th day of my participation in Gwen Challenge

Grouping of letter Heterotopic Words (49)

Topic describes

Given an array of strings, group alphabetic allotopic words together. An anagram is a string with the same letters but different arrangements.

Example 1:

Input: [" eat ", "tea", "tan", "ate" and "NAT" and "bat"] output: [[" ate ", "eat", "tea"], [" NAT ", "tan"], [" bat "]]Copy the code

instructions

  • All input is lowercase.
  • Regardless of the order in which the answers are printed.

Thought analysis

We can use a hash table to do this. First, when we get each item in the array, we first sort the item as the key of the hash table. Value is a list of unsorted items (but each item is equal to the key), so we walk through the array. Finally, we store the values from the HashMap into the array we need.

The code shown

Solution a: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (n) (n)} {O 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;

    }
Copy the code

Relative sorting of arrays (1122)

Topic describes

I give you two arrays, arr1 and arR2,

  • arr2The elements in the
  • arr2Each element in thearr1 中

Sort the elements in ARR1 so that the relative order of the items in ARR1 is the same as that in ARR2. Elements that do not appear in ARR2 need to be placed at the end of ARR1 in ascending order.

Example 1:

Input: arr1 =,3,1,3,2,4,6,7,9,2,19 [2], arr2 =,1,4,3,9,6 [2] output:,2,2,1,4,3,3,9,6,7,19 [2]Copy the code

Tip:

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2The elements in thearr2[i]Each are not identical
  • arr2Each element inarr2[i]inarr1 中

Thought analysis

We can also use a hash table for this problem. We can first store the value of array 1 in the hash table, increment the value of array 2 if the key is the same, and then store the value of array 2 in another hash table.

Finally, we first collate the arR2 numbers in ARR1, add them to the target array (according to the hash table to determine whether there is arR2), and finally put the remaining arR1 values into the target array.

The code shown

Solution a: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (n) (n)} {O O (n).

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

// input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] each element in arr2 appears in arr1
// output: [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);
        }

        // select arr2 from arr1
        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; }}// A temporary array of values that do not exist in arr2
        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;

    }
Copy the code

conclusion

Hash table solution, a lot of times to simplify the problem solving process, but also can not avoid the increase of space complexity. It needs to be treated as appropriate according to the title.