Hi coders,
I was wondering of a way to sort a 2-D structure in which one set has keys and other has value.
For eg-
A={0,7,4,7}
B={0,1,2,3}
B has the keys and A has the value.After sorting the arrays should be:
A={0,4,7,7}
B={0,2,1,3}
What is the best way to do this?What will be the best data structure for this?
I feel that HashMap can do it.but i have problems implementing it.
I was wondering of a way to sort a 2-D structure in which one set has keys and other has value.
For eg-
A={0,7,4,7}
B={0,1,2,3}
B has the keys and A has the value.After sorting the arrays should be:
A={0,4,7,7}
B={0,2,1,3}
What is the best way to do this?What will be the best data structure for this?
I feel that HashMap can do it.but i have problems implementing it.
You can simply create a class containg these two variables (key and value) and then implement a comparator that compares two objects of that class according to required values. After that you will only use an array of references to objects, each representing one pair key-value.
Another trick is to use one int or long variable to store two values in case they fits in it. For example, if we have a maximum limit of 1000, we know it will fit in 10 bits (1000<2^10), so we can store both key and value in one 32-bit int. Thus, we can do something like that: int combined = (a<<10) | b; in case we want to sort according to a. Query for a and b can be made like that: a = combined>>10; b = combined&1023;
class ValueComparator implements Comparator {
Map base;
public ValueComparator(Map base) {
this.base = base;
}
public int compare(Object a, Object b) {
if((Double)base.get(a) < (Double)base.get(b)) {
return 1;
} else {
return -1;
}
}
}
ValueComparator comp=new ValueComparator(m);
TreeMap<Integer,Double> tree=new TreeMap<Integer,Double>(comp);
tree.putAll(m);
Why are you using a map? The goal of the special class with Comparator is to avoid all complicated and unnecessary data structures. You can do something like this:
class Pair implements Comparable<Pair> {int a,b;
public Pair(int a, int b) {
this.a = a; this.b = b;
}
@Override
public int compareTo(Pair other) {
if (a==other.a) return 0;
if (a>other.a) return 1;
return -1;
}
}
Then you will only create an array of Pair, and sort it by a standard way (Arrays.sort(arr);).