Remove element from an array (code-specific)

Question

The user enters x-amount of integers, which are stored in an array ('dataA'). The average of the data is calculated, and the element, which is furthest should be removed ('outlier'). I don't know how to remove the element and need to know.

Also, the program removes one outlier, it calculates the new average and removes the next outlier until there is one element left.

public static Scanner sc1 = new Scanner(System.in);
public static int dataN = sc1.nextInt();//number of data elements
public static double[] dataA = new double[dataN];//array storing elements

for(int index = 0; index<dataA.length; index++)//increments index
    {
        double lengthA = dataA.length;//length of array
        double avg = sum/lengthA;//avg of elements

        double outlier = dataA[0];//outlier
        double index_outlier = 0;//index of outlier

        double dif_in = Math.abs(avg - dataA[index]);//difference of avg & element
        double dif_out = Math.abs(avg - outlier);//difference of avg & outlier

        if(dif_in > dif_out)
        {
            outlier = dataA[index];
            index_outlier = index;      
        }

Arrays have a fixed size... that means you can't change the length of an array, all you can do is make a new array with a different size. — user253751, May 11 '15 at 22:43
Right, so I don't need the size to change. Just to remove the element. — Ben, May 11 '15 at 22:45
_the element, which is furthest should be removed_ What exactly does this mean? — ZachSand, May 11 '15 at 22:47
You could search 'how to remove an element from an array' on Stack Overflow. http://stackoverflow.com/questions/642897/removing-an-element-from-an-array-java — mcraenich, May 11 '15 at 22:48
@ben1123 Well, "remove" implies the array is smaller after you remove something from it. (It contains everything it contained before, except for the thing you removed; therefore, it contains less things) — user253751, May 11 '15 at 22:49
@ben1123 Do you actually need to mutate the array or need to get the element that is left last? — , May 11 '15 at 22:51
@Jaagup I need to remove each outlier individually, not just determine the element that is last... if that's what you mean — Ben, May 11 '15 at 22:52
@immibis, can I replace it with some sort of null value? (not zero) — Ben, May 11 '15 at 22:53
you could swap it to the end of the array and in the next step just iterate until you hit the end-1.. — h3n, May 11 '15 at 22:57
@ben1123 Java arrays are fixed-sized, so you can't remove elements from it by definition. Is creating new arrays an option? Is performance a concern? Can the order of elements in array be changed? — , May 11 '15 at 22:57
You can try to swap the outlier with last element of Array and continue with array but consider one less element. No need to remove as such. — akhil_mittal, May 12 '15 at 02:05

score 1 · Answer 1 · answered May 11 '15 at 22:53

1

Best solution would be to create a new array that copies the elements from the previous one except for the one you want to delete (with a for loop and an array with 1 less space than yours) and then set your original array as the new one.

answered May 11 '15 at 22:53

Azerogg

93
8

How do I copy all the elements without the outlier? The number of elements inputted originally vary. – Ben May 11 '15 at 22:56
For (int i=0,i<(originalSize),i++){ Array2[i]==Array1[i]}. – Azerogg May 12 '15 at 09:09

score 1 · Answer 2 · answered May 11 '15 at 23:00

Since you need a variable size data structure use a LinkedList instead of primitive array.

Also a better solution to do this will be as follows: 1) Store all the values in a LinkedList. Sort it while add elements to the list using insertion sort or sort it after adding all elements using Collections.sort(list). 2) Find the average. This can be done while adding the elements in the list. No need to iterate over the list again. 3) Since all the values are in sorted manner, the outlier will be either the first or the last element in the LinkedList. Compare the diff_first and diff_last and remove the greater. 4) Recompute the average. For this you can use a very simple equation: new_avg = ((avg*l)-outlier_value)/(l-1); where l = number of values for which avg was calculated. 5) Repeat step 3 and 4 until only 1 element is left in the LinkedList.

Why `LinkedList` rather than `ArrayList`? `LinkedList` is slower at 90% of the things people do. — user253751, May 11 '15 at 23:59
I agree that LinkedList are slower than ArrayList but that is only when you are traversing through the list again and again. Whereas in this case the LinkedList is created only once. We need to look at the first and the last element of the list which is an O(1) operation since we always have reference to head and tail of the list. — abhishrp, May 15 '15 at 00:01

score 1 · Accepted Answer · answered May 12 '15 at 02:07

You can try to swap the outlier with last element of Array and continue with array but consider one less element. In case you are fine with it then you can use Array like:

public static void main(String[] args) throws FileNotFoundException {
        double[] dataArray = new double[] {1.5,2.5,3.5,4.5,7.5,8.5,2.5};
        int arraySizeToConsider = dataArray.length;
        double outlier;
        int index_outlier;
        double avg;
        double diffInOutlierAndAvg;

        while(arraySizeToConsider > 0) {
            outlier = dataArray[0];
            index_outlier = 0;
            avg = computeSum(dataArray,arraySizeToConsider) / (arraySizeToConsider);//avg of elements
            diffInOutlierAndAvg = Math.abs(avg - outlier);

            // find outlier
            for(int index = 0; index<arraySizeToConsider; index++)//increments index
            {
                if(Math.abs(avg - dataArray[index]) > diffInOutlierAndAvg) {
                    outlier = dataArray[index];
                    index_outlier = index;
                }
            }
            double temp = dataArray[arraySizeToConsider -1];
            dataArray[arraySizeToConsider -1] = outlier;
            dataArray[index_outlier] = temp;
            arraySizeToConsider = arraySizeToConsider -1;
            System.out.println("Average: " + avg + " Outlier: " + outlier + " index " + index_outlier + " array size to consider: " +arraySizeToConsider);
        }
    }
    private static double computeSum(double[] array, int arraySizeToConsider) {
        double sum = 0;
        for (int i = 0; i < arraySizeToConsider; i++) {
            sum = sum + array[i];
        }
        return sum;
    }

And here is the output:

Average: 4.357142857142857 Outlier: 8.5 index 5 array size to consider: 6 Average: 3.6666666666666665 Outlier: 7.5 index 4 array size to consider: 5 Average: 2.9 Outlier: 4.5 index 3 array size to consider: 4 Average: 2.5 Outlier: 1.5 index 0 array size to consider: 3 Average: 2.8333333333333335 Outlier: 3.5 index 2 array size to consider: 2 Average: 2.5 Outlier: 2.5 index 0 array size to consider: 1 Average: 2.5 Outlier: 2.5 index 0 array size to consider: 0

There are some more optimizations that I have left to you to figure out.

Hint: Do we need to compute sum every time we find an outlier ;)?

Hmmm... i'll have to think about that one – Ben May 12 '15 at 02:09 — Ben, May 12 '15 at 02:09

Remove element from an array (code-specific)

3 Answers3