开发者

Efficient code to do array matching in Java

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,开发者_JS百科 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}


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]


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;
    }
}


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));
   }
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜