Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How print indexes of 10 smallest values in array

I need select 10 smallest numbers from array(with 2 000 items) and print their indexes.

At first I tried just sorted this array and print values array[0 to 9]. It was the smallest numbers but I lost indexes of this values, which they had i non-sorted array.

Second option was tried use treeMap which works well, but when I have two equal keys it print only one of them, but I need print both of them.

Example of use code with treeMap:

  TreeMap<Integer, String> treemap = new TreeMap<Integer, String>();

  treemap.put(2, "two");
  treemap.put(1, "one");
  treemap.put(3, "three");
  treemap.put(6, "six");
  treemap.put(6, "six2");
  treemap.put(5, "five");      

  Collection<String> coll=treemap.values();
  System.out.println("Value of the collection: "+coll);  

Until now I don't use treeMap, so is possible, that exist some easy way how fix it. Or is better use something else?

I will be grateful for any help

like image 505
Petr Šrámek Avatar asked Nov 02 '13 14:11

Petr Šrámek


2 Answers

It was the smallest numbers but I lost indexes of this values, which they had i non-sorted array

Then why don't you just create a class to hold this indexes ? Then just sort your array by value and you'll get the index associated.

class MyClass implements Comparable<MyClass>{
    private int index;
    private int value;

    public MyClass(int i, int v){
       this.index = i;
       this.value = v;
    }

    @Override
    public String toString(){
        return "Index: "+index+" Value: "+value;
    }

    @Override
    public int compareTo(MyClass m) {
        return value - m.value;
    }
}

public static void main(String[] args){   
    MyClass[] array = new MyClass[20];

    for(int i = 0; i < array.length; i++){
       array[i] = new MyClass(i, someRandomValue); // Here I used (i*3 + 2)%5
    }
    System.out.println(Arrays.toString(array));
    Arrays.sort(array);
    MyClass [] arraySorted = Arrays.copyOfRange(array, 0, 10); //take the first ten elements
    System.out.println(Arrays.toString(arraySorted));
}


Note :

If you want to sort objects that have the same value by indexes, you can modify your comparator like this :

@Override
public int compareTo(MyClass m) {
    int compareValue = value - m.value;
    if(compareValue == 0)
        return index - m.index;
    return compareValue;
}


Output (with the second compareTo method) :
Before :
[Index: 0 Value: 2, Index: 1 Value: 0, Index: 2 Value: 3, Index: 3 Value: 1, Index: 4 Value: 4, Index: 5 Value: 2, Index: 6 Value: 0, Index: 7 Value: 3, Index: 8 Value: 1, Index: 9 Value: 4, Index: 10 Value: 2, Index: 11 Value: 0, Index: 12 Value: 3, Index: 13 Value: 1, Index: 14 Value: 4]

After :
[Index: 1 Value: 0, Index: 6 Value: 0, Index: 11 Value: 0, Index: 3 Value: 1, Index: 8 Value: 1, Index: 13 Value: 1, Index: 0 Value: 2, Index: 5 Value: 2, Index: 10 Value: 2, Index: 2 Value: 3]
like image 189
Alexis C. Avatar answered Sep 18 '22 07:09

Alexis C.


Instead of sorting bare values, sort (value, index) pairs, in respect to the value. Then, you just take first 10 pairs and you have 10 origin indices.

For example, you want to sort:

6 2 7 4

Making (value, index) pairs:

(6, 0) (2, 1) (7, 2) (4, 3) 

Sorting in respect to value:

(2, 1) (4, 3) (6, 0) (7, 2) 

Indices:

1 3 0 2

Your approach with TreeMap is fine. The only modification you have to make looks like this:

class Pair implements Comparable<Pair> {
    int value;
    int index;

    @Override
    int compareTo(Pair other) { return value - other.value };
}

Map<Pair, String> map = new TreeMap<Pair, String>();
like image 40
Adam Stelmaszczyk Avatar answered Sep 22 '22 07:09

Adam Stelmaszczyk