java - 在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 之间。对于 arrayOne 中的每个 i，我希望能够将 i 映射到 arrayTwo< 中的 j/code> 例如 arrayOne[i] = arrayTwo[j] (1)。如果 arrayTwo[] 中不存在满足 (1) 的 j，则将 i 映射到满足 (1) 的 k具有与 i 最接近的 int 值。

输出应该是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

我将创建一个按 arrayTwo 的值排序的 TreeMap 并映射到索引的 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]