Finding the desired amount of smallest Doubles in an ArrayList

Question

I have an ArrayList filled with Double values, and based on user input (an int), I need to find the indices of the entered amount of smallest Doubles from this List. For example, if the user were to type in 5, and the ArrayList looked as such (is actually much bigger):

-6789.44658
-27239.73827
-12365.78370
-456.789457
-4768.42579
-15263.26399
-15263.26399
-0.0
-24688.7289

I would get 1, 5, 8, 2, 6(order of the 5 smallest Doubles in terms of least to greatest doesn't matter). Here's what I have so far:

int[] indices = new int[input];
List<Double> copy = new ArrayList<Double>(origList); //origList is list of Doubles

for (int t = 0; t < input; t++)
{
    indices[t] = origList.indexOf(Collections.min(copy));
    copy.remove(Collections.min(copy));
}

There are 2 problems with this though:

1. it's really inefficient
2. in the example ArrayList given above, two of the values are the same (there could even be three values that are the same). If identical values are the lowest values in copy, because indexOf() returns the index of the first occurrence of this value in
   origList,the same index is returned twice. But, none of the indices can be the same.

Thanks for any help!

Answer 1

One solution is to take your origList and iterate over it once populating a TreeMap<Double, List<Integer>> with the values. Where the key is your double and the list is the list of indices that have that value.

A TreeMap maintains order as you add items to it so there is no need to do an additional sorting step. Puts into a TreeMap are log(n) so time to find the smallest n indices should be O(log N).

   int input = 5;
   List<Double> origList = new ArrayList<Double>();

   origList.add(-6789.44658);
   origList.add(-27239.73827);
   origList.add(-12365.78370);
   origList.add(-456.789457);
   origList.add(-4768.42579);
   origList.add(-15263.26399);
   origList.add(-15263.26399);
   origList.add(-0.0);
   origList.add(-24688.7289);

   TreeMap<Double, List<Integer>> smallest = new TreeMap<Double, List<Integer>>();
   for (int i = 0; i < origList.size(); i++) {
       double d = origList.get(i);
       List<Integer> list = smallest.get(d);
       if (list == null) {
           list = new ArrayList<Integer>();
           smallest.put(d, list);
       }
       list.add(i);
   }

Now that you have a sorted Map of your values to their indices you just need to get the first n keys out of that map and get their values and you are done.

   List<Integer> indices = new ArrayList<Integer>();

   for (Double key : smallest.keySet()) {
       List<Integer> list = smallest.get(key);
       for (Integer index : list) {
           indices.add(index);
           if (indices.size() == input) break;
       }
       if (indices.size() == input) break;
   }

   System.out.println(smallest);
   System.out.println(indices);

The above code produces the following map:

{-27239.73827=[1], -24688.7289=[8], -15263.26399=[5, 6], -12365.7837=[2], -6789.44658=[0], -4768.42579=[4], -456.789457=[3], -0.0=[7]}

and the following final output:

[1, 8, 5, 6, 2]

Answer 2

How about something like this?

public int[] getLowest(List<Double> list, int howMany) {
    int[] indices = new int[howMany];

    List<Double> copy = new ArrayList<>(list);
    Collections.sort(copy);

    List<Double> lowest = new ArrayList<>();
    for (int i = 0; i < howMany; i++) {
        lowest.add(copy.get(i));
    }

    int indicesIndex = 0;
    for (int d = 0; d < list.size(); d++) {
        if (lowest.contains(list.get(d))) {
            indices[indicesIndex] = d;
            indicesIndex++;
        }
    }

    return indices;
}

Answer 3

I iterate through the double List, keeping the n smallest values and ignoring duplicates.

Here's the result.

[(-27239.73827, 1), (-24688.7289, 8), (-15263.26399, 5), (-12365.7837, 2), 
 (-6789.44658, 0)]

I realize I returned the doubles and the indices. You can get just the indices from the Minimum array if you wish.

This code runs in O(n).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NSmallest implements Runnable {

    private static final double LARGE_DOUBLE = 1.0E100;

    private int n;

    public static void main(String[] args) {
        int n = 5;
        new NSmallest(n).run();
    }

    public NSmallest(int n) {
        this.n = n;
    }

    @Override
    public void run() {
        List<Double> numbers = loadList();
        Minimum[] minimums = initializeMinimums();

        for (int i = 0; i < numbers.size(); i++) {
            double value = numbers.get(i);
            minimums = getMinimum(minimums, value, i);
        }

        System.out.println(Arrays.toString(minimums));
    }

    private List<Double> loadList() {
        List<Double> numbers = new ArrayList<>();
        numbers.add(Double.valueOf(-6789.44658));
        numbers.add(Double.valueOf(-27239.73827));
        numbers.add(Double.valueOf(-12365.78370));
        numbers.add(Double.valueOf(-456.789457));
        numbers.add(Double.valueOf(-4768.42579));
        numbers.add(Double.valueOf(-15263.26399));
        numbers.add(Double.valueOf(-15263.26399));
        numbers.add(Double.valueOf(-0.0));
        numbers.add(Double.valueOf(-24688.7289));

        return numbers;
    }

    private Minimum[] initializeMinimums() {
        Minimum[] minimums = new Minimum[n];

        for (int i = 0; i < minimums.length; i++) {
            minimums[i] = new Minimum(LARGE_DOUBLE, -1);
        }

        return minimums;
    }

    private Minimum[] getMinimum(Minimum[] minimums, double value, int index) {
        for (int i = 0; i < minimums.length; i++) {
            double number = minimums[i].getNumber();
            if (value == number) {
                break;
            } else if (value < number) {
                int j = minimums.length - 2;
                while (j >= i) {
                    minimums[j + 1].setIndex(minimums[j].getIndex());
                    minimums[j + 1].setNumber(minimums[j].getNumber());
                    j--;
                }
                minimums[i].setIndex(index);
                minimums[i].setNumber(value);
                break;
            }
        }

        return minimums;
    }

    public class Minimum {
        private double number;
        private int index;

        public Minimum(double number, int index) {
            this.number = number;
            this.index = index;
        }

        public double getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }

        public void setNumber(double number) {
            this.number = number;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("(");
            builder.append(number);
            builder.append(", ");
            builder.append(index);
            builder.append(")");
            return builder.toString();
        }

    }
}