Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

phantom11's blog

Sorting keys on the basis of value in Java
By phantom11, 13 years ago, In English
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.
  • Vote: I like it
  • +7
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +13 Vote: I do not like 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;

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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);
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply