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);).
HashMap would do only if you have set of unique keys. For your array "A" it is not so.
However, you just should not keep your "keys and values" separately.
int[][] ab = new int[][]{{0,0},{7,1},{4,2},{7,3}}; Arrays.sort(ab, new Comparator<int[]>{ public int compareTo(int[] x, int[] y){ return Integer.signum(x[0] - y[0]);}});(you can often see this in other people solutions)
And never name variables with CAPITAL LETTERS!
Use this class:
class Point implements Comparable<Point> {
int x, y;
Point(int xx, int yy) { x = xx; y = yy; }
public int compareTo(Point p) {
if (this.x == p.x) return this.y - p.y;
return this.x - p.x;
}
}
and TreeSet<Point> or Point[], then Arrays.sort()