How do I sort an array so it has the same order as another array?

Question

I have two arrays

int arr1 [] = {4, 6, 2, 6, 4, 8, 12, 14, 18, 4, 38};
int arr2 [] = {4, 2, 8, 6, 18, 12};

arr1 contains every value of arr1, sometimes multiple.

arr2 contains every value only once.

The order of the elements in arr1 should be the same as the order of the elements in arr2.

Elements that are in arr1 but not in arr2 should be appended to the end in the same order.

This is how they should look in the end:

new arr1[] = {4, 4, 4, 2, 8, 6, 6, 18, 12, 14, 38};

Here´s what I tried:

int [] temp = new int [arr1.length];

for (int i = 0; i<arr.length; i++){
    if (arr2[i] == arr1[i]){
        temp[arr2[i]] == arr1[i];
    }
}
for (int k = 0; k<arr1.length; k++){
    arr1[k] == temp[k];
    arr2[k] == k; 
}

If this were my problem, I'd try to work out an algorithm using pencil and paper, and then commit it to code. You'll need to nest loops to be sure,... work it out, and you'll come up with something that even if it doesn't bring a solution, would at least allow you to improve the question. — Hovercraft Full Of Eels, Nov 18 '19 at 01:25
Actually, calling `Arrays.sort(...)` using a Comparator that uses the 2nd array to decide the compare method's return value would work well here too — Hovercraft Full Of Eels, Nov 18 '19 at 01:25
*The order of the elements in arr1 should be the same as the order of the elements in arr2.* `int arr1 [] = {4, 6, 2, 6...` `int arr2 [] = {4, 2, 8, 6...` they're not in order? — FailingCoder, Nov 18 '19 at 01:25
[How to sort an array of ints using a custom comparator](https://stackoverflow.com/questions/3699141/how-to-sort-an-array-of-ints-using-a-custom-comparator) — FailingCoder, Nov 18 '19 at 01:28
@KnowNoTrend look at the new array-> arr1 new. All its numbers except those that arent in arr2 are in the same position. — asaea, Nov 18 '19 at 01:28
No, I have checked. arr1 starts with `4, 6` and arr2 starts with `4, 8`. Additionally, arr1 has no `8` before any `6`. — FailingCoder, Nov 18 '19 at 01:29
@KnowNoTrend look again... the array at the bottom of my question has the same order as arr2. I think you dont understand my problem. — asaea, Nov 18 '19 at 01:30
@KnowNoTrend: he's trying to emulate the order of the 2nd array into the 1st, not put things in *numeric* order — Hovercraft Full Of Eels, Nov 18 '19 at 01:31
But having said that, @asaea, again this question would be improved greatly if you would show the fruits of your own efforts in the question itself. You have tried something before coming here, right? — Hovercraft Full Of Eels, Nov 18 '19 at 01:33
Oh, alright, I get it now. You want to use the order in array 2 to determine how array 1 is sorted; if a `-1` were to be placed at the last index of array 2, then it would place all the `-1`s in array 1 at the end of the array? — FailingCoder, Nov 18 '19 at 01:37

kaya3 · Answer 1 · 2019-11-18T01:44:24.267

You can do this without using a sorting algorithm, in O(n) time and O(n) auxiliary space. The trick is to count how many times each element of arr2 occurs in a Map, and then use the counts to write that many copies to arr1, using arr2 to get them in the right order.

To keep the same order for those elements missing from the arr1, store them in a list instead of counting them, and then write them back to arr1 at the end.

import java.util.*;

class Solution {
    public static void sortArrayByOtherArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> counts = new HashMap<>();
        List<Integer> extras = new ArrayList<>();

        // initialise counter Map
        for(int x : arr2) {
            counts.put(x, 0);
        }

        // count occurrences, and populate extras list
        for(int x : arr1) {
            if(counts.containsKey(x)) {
                counts.put(x, counts.get(x) + 1);
            } else {
                extras.add(x);
            }
        }

        // write c copies of each x, in order from arr2
        int i = 0;
        for(int x : arr2) {
            int c = counts.get(x);
            for(int j = 0; j < c; ++j) {
                arr1[i++] = x;
            }
        }

        // write the extras
        for(int x : extras) {
            arr1[i++] = x;
        }
    }
}

How do I sort an array so it has the same order as another array?

1 Answers1