Efficient code to do array matching in Java

Question

So I have the two array of size 256 like this:

int arrayOne[] = {1, 5, 8, 100, 100, 5, 66, ..., 255} //random order

int arrayTwo[] = {101, 8, 9, 22, 90 , 22, ...., 174}

values inside the array are between 0 to 255. For every i in arrayOne, I want to be able to map i to j in arrayTwo such as arrayOne[i] = arrayTwo[j] (1). If there is no such j in arrayTwo[] that satisfies (1), i is mapped to k that has the closest int value to i.

The output should be arrayThreethat contains the final mapping explained above.

Sample:

int arrayOne[] = {1, 50, 100, 50, 100, 22, 23, 26} //input array

int arrayTwo[] = {1, 45, 22, 23, 52, 90, 100, 99} //array that contains values to match against input array

int arrayThree[] = {0, 4, 6, 4, 6, 2, 3, 3} //output array that contains the matches.

ACID test:

int arrayOne[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 7, 9, 10, 11, 12, 12, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 31, 32, 33, 34, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 61, 62, 63, 64, 64, 65, 65, 66, 66, 67, 67, 68, 68, 68, 69, 69, 69, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 74, 74, 74, 75, 75, 76, 77, 79, 81, 84, 87, 90, 93, 98, 103, 109, 115, 123, 130, 138, 145, 151, 157, 165, 173, 181, 191, 200, 210, 219, 227, 233, 238, 240, 242, 243, 244, 245, 246, 247, 248, 249, 249, 250, 251, 251, 251, 252, 252, 253, 253, 253, 253, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 255, 255}

int arrayTwo[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 11, 16, 20, 21, 22, 23, 23, 24, 25, 26, 27, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39, 41, 43, 45, 47, 48, 50, 52, 54, 56, 58, 59, 61, 62, 64, 65, 67, 68, 69, 71, 72, 73, 74, 75, 75, 76, 77, 77, 78, 79, 79, 80, 80, 81, 81, 81, 81, 82, 82, 82, 82, 82, 82, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85, 86, 88, 90, 93, 96, 101, 106, 112, 118, 125, 131, 137, 144, 153, 162, 173, 184, 194, 202, 211, 220, 228, 236, 243, 247, 250, 251, 252, 252, 253, 253, 253, 253, 253, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254}

Output generated by my code and dacwe code:

int myOutput[] = {0, 0, 0, 0, 0, 0, 0, 0, 8, 10, 10, 10, 10, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 18, 18, 19, 19, 20, 21, 21, 23, 24, 24, 25, 26, 27, 28, 29, 29, 30, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 45, 45, 45, 46, 47, 47, 47, 48, 48, 49, 49, 49, 49, 50, 50, 50, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 56, 56, 58, 59, 62, 66, 99, 124, 126, 127, 128, 129, 130, 131, 132, 133, 136, 137, 137, 138, 139, 139, 140, 141, 142, 143, 144, 145, 146, 147, 147, 147, 147, 148, 148, 148, 148, 149, 149, 149, 149, 150, 150, 150, 151, 151, 153, 153, 153, 153, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158}


int dacweOutput[] = {7, 7, 7, 7, 7, 7, 7, 7, 8, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 19, 19, 20, 22, 22, 23, 24, 24, 25, 26, 27, 28, 29, 29, 30, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 39, 39, 40, 40, 41, 41, 42, 42, 43, 43, 44, 45, 45, 45, 46, 47, 47, 47, 48, 48, 49, 49, 49, 49, 50, 50, 50, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 57, 57, 58, 60, 63, 69, 121, 125, 126, 127, 128, 129, 131, 132, 133, 134, 135, 136, 137, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 146, 147, 147, 147, 147, 148, 148, 148, 148, 149, 149, 149, 150, 150, 150, 152, 152, 157, 157, 157, 157, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}

your first condition can be achieved by converting array to ArrayList.But it is difficult to achieve second condition i think. — Android Killer
– Android Killer, Commented Oct 6, 2011 at 7:00
I am doing it as we speak, I will post my answer soon and see if anyone has any better idea. — Tu Hoang
– Tu Hoang, Commented Oct 6, 2011 at 7:01

dacwe · Accepted Answer · 2011-10-06 09:26:28Z

6

I would create a TreeMap sorted by value of arrayTwo and map to an Integer of the index. Then I would simply iterate arrayOne and get the closest match:

public static void main(String[] args) throws Exception {

    int arrayOne[] = {1, 50, 100, 50, 100, 22, 23, 26};
    int arrayTwo[] = {1, 45, 22, 23, 52, 90, 100, 99};


    TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < arrayTwo.length; i++)
        if (!map.containsKey(arrayTwo[i])) // if you want it to choose the first
            map.put(arrayTwo[i], i);

    int arrayThree[] = new int[arrayOne.length];

    for (int i = 0; i < arrayThree.length; i++) {
        int v = arrayOne[i];

        Integer h = map.higherKey(v - 1);
        Integer l = map.lowerKey(v);

        arrayThree[i] = map.get(l !=null && (h ==null || v - l < h - v) ? l : h);
    }

    System.out.println(Arrays.toString(arrayThree));
}

Output:

[0, 4, 6, 4, 6, 2, 3, 3]

edited Oct 6, 2011 at 9:26

answered Oct 6, 2011 at 7:03

dacwe

43.6k12 gold badges118 silver badges142 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Android Killer Over a year ago

very nice idea buddy.+1 for it.

dacwe Over a year ago

Which input do we differ on, and which of our solutions produce the correct result?

Tu Hoang Over a year ago

That I am not sure. The input used are 2 arrays of size 256. The problem is that I am not sure which produces the correct result. I can post the input up here if you are interested.

Tu Hoang Over a year ago

I think I know why. Your code doesn't catch the case when the value is already found, but instead it keeps looking to the right. As the result arrayOne[0] should be mapped to arrayTwo[0] but yours maps its to the 7th element which is incorrect and will result in the output shifted to the right.

dacwe Over a year ago

-1? For what? First, since arrayTwo can contain the same number more than once all the indexes pointing to the same value are correct (both index 0 and I output 7 are correct). If you still want it to choose the first, add a if (!map.containsKey(arrayTwo[i])) before putting it into the map. Secondly, your indexes are messed up, for the value 9 you choose that the closest value is 5 (index=10) when clearly 11 (index=11) is closer.

|

ControlPower · Accepted Answer · 2011-10-06 07:30:39Z

please try:

package javatest;
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int arrayOne[] = {1, 50, 100, 50, 100, 22, 23, 26};
        int arrayTwo[] = {1, 45, 22, 23, 52, 90, 100, 99};
        int arrayThree[] = new int[arrayTwo.length];
        ValueIndexPair[] arr = new ValueIndexPair[arrayTwo.length];
        for(int i = 0; i < arrayTwo.length; i++) {
            arr[i] = new ValueIndexPair(arrayTwo[i], i);
        }
        Arrays.sort(arr);
        ValueIndexPair temp = new ValueIndexPair(0, 0);
        for(int i = 0; i < arrayOne.length; i++) {
            temp.setValue(arrayOne[i]);
            int index = Arrays.binarySearch(arr, temp);
            if(index >= 0) {
                arrayThree[i] = arr[index].getIndex();
            } else{
                index = index * -1 - 1;
                if(index == 0) {
                    arrayThree[i] = arr[0].getIndex();
                } else if(index == arrayTwo.length){
                    arrayThree[i] = arr[arrayTwo.length - 1].getIndex();
                } else {
                    int v1 = arr[index - 1].getValue();
                    int v2 = arr[index].getValue();
                    if(arrayOne[i] - v1 > v2 - arrayOne[i]){
                        arrayThree[i] = arr[index].getIndex();
                    }else{
                        arrayThree[i] = arr[index - 1].getIndex();
                    }
                }                
            }                
        }

        for(int i = 0; i < arrayThree.length; i++){
            System.out.println(arrayThree[i]);
        }            
    }
}
class ValueIndexPair implements Comparable<ValueIndexPair> {
    private int value;
    private int index;

    public ValueIndexPair(int value, int index){
        this.value = value;
        this.index = index;
    }

    public int getValue() {
        return this.value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getIndex(){
        return this.index;
    }

    public int compareTo(ValueIndexPair obj) {
        return this.value - obj.value;
    }
}

Fredrik LS · Accepted Answer · 2011-10-06 09:17:02Z

Here is a sligthly different one. Do a binary search for the value, if not found, check if it maps to the first or last element of arrayTwo if not find the value in arrayTwo which is closest to the given value:

    public static void main(String[] args)
   {
      int arrayOne[] = {0, 11, 12, 6, 7, 3};
      int arrayTwo[] = {1, 10};
      Arrays.sort(arrayTwo);
      int arrayThree[] = new int[arrayOne.length];

      for (int i = 0; i < arrayOne.length; i++)
      {
         int index = Arrays.binarySearch(arrayTwo, arrayOne[i]);

         if (index >= 0)
         {
            //If we found a match
            arrayThree[i] = index;
         } else {
            int ind = Math.abs(index + 1);

            if (ind == arrayTwo.length)
            {
               //If end of arrayTwo
               arrayThree[i] =  arrayTwo.length - 1;
            } else if (ind == 0) {
               //If beginning of arrayTwo
               arrayThree[i] = 0;
            } else {
               //Find the closest value in arrayTwo.               
               arrayThree[i] = Math.abs(arrayTwo[ind - 1] - arrayOne[i]) <= Math.abs(arrayTwo[ind] - arrayOne[i]) ? ind - 1 : ind;
            }

         }
      }

      System.err.println(Arrays.toString(arrayThree));
   }

Collectives™ on Stack Overflow

Efficient code to do array matching in Java

3 Answers 3

6 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

Comments

Comments

Related