Эффективный код для сопоставления массивов в Java

Question

Итак, у меня есть два массива размером 256, например:

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

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

значения внутри массива находятся в диапазоне от 0 до 255. Для каждого i в arrayOne я хочу иметь возможность сопоставлять i с j в arrayTwo, например arrayOne[i] = arrayTwo[j] (1). Если в arrayTwo[] нет такого j, которое удовлетворяет (1), i сопоставляется с k, которое имеет самое близкое значение int к i.

Выходные данные должны быть arrayThree, которые содержат окончательное отображение, описанное выше.

Пример:

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.

КИСЛОТНЫЙ тест:

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}

Вывод, сгенерированный моим кодом и dacwe кодом:

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}

---

Answer 1

Я бы создал TreeMap, отсортированный по значению arrayTwo и сопоставил бы с Integer индекса.Тогда я просто перебрал бы arrayOne и получил бы самое близкое совпадение:

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

Вывод:

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

Answer 2

пожалуйста, попробуйте:

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

Answer 3

Вот немного другой. Выполните двоичный поиск значения, если оно не найдено, проверьте, соответствует ли оно первому или последнему элементу arrayTwo, если не найдено значение в arrayTwo, которое ближе всего к данному значению:

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