Блог пользователя phantom11

Автор phantom11, 13 лет назад, По-английски
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.
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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;

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I implemented your first thought as this but then I cannot put or remove elements from this treemap once initialized...
    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);
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Sometimes I just can not help thinking how easy it is to program in Ruby:
a = [0, 7, 4, 7]
b = [0, 1, 2, 3]
zipped_array = a.zip(b)
zipped_array.sort!()
a, b = zipped_array.transpose()

Or even the shorter form:
a, b = a.zip(b).sort!().transpose()

If only programs in Ruby were a bit better with regard of execution time.
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
HashMap and HashSet don't sort their elements. Only TreeMap and TreeSet do it.

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()