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 arrayThree
that 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));
}
精彩评论