Reputation: 49

Checking for Duplicates in an Array Backwards

This is the same person who had trouble with the last array problem just one or two days ago. We've a new assignment which asks us to find and replace duplicates in an array of randomly generated numbers. I wrote a code and sent it to my teacher for feedback; she responded with this solution:

So, take the first random num and store into the first slot (this can be done before the loop). Then, start a loop that creates the second random num and tests backwards to see if there are duplicates from the ones already stored. So, a backwards loops that tests for duplicates and counts down to 0 from the current location and replaces duplicates. Once that test passes, then you'll go to the next element, create a new random number, and then test the ones before it for duplicates.

I've done this here, and it's reduced the number of randomly generated numbers, but I still run into the stray duplicate:

import java.lang.Object;
    import java.util.Random;

public class Prog433a {

    public static void main(String[]args) {

        Random randslct = new Random();

        int[] list = new int[20];
        int counter = 0;
        int index = 0;
        int min2 = 0;


        System.out.println("\nAfter");

        for (int k = 0; k < list.length - 1; k++) {
            list [k] = randslct.nextInt(30) + 1;
            for (int z = list.length - 1; z >= 0; z--) {
                if (list[k] == list[z] && z!=k) {
                    while (list[k] == list[z]) {
                        list [k] = randslct.nextInt(30) + 1; 
                    }
                }
            }
        }

        int min = list[0];
        while (counter < list.length - 1) {
            for (int x = 0; x < list.length - 1; x++) { // scroll through the indexes.
                if (list[x] < min) {
                    min = list[x];
                    index = x; // keep the index of the biggest number.
                } 
            }
            System.out.println(list[index]);
            min = 100 * (list[index]);

            list[index] = 100 * (list[index]); // change the value in the original array so it won't find the same max again
            counter++;
        }
    }
}

System Output:

I posted my output towards the bottom. Because this is an introductory coding class, I'd prefer if the solution did not involve Sets or any of the like. But alas, beggars cannot be choosers.

Is there something I have forgotten to add?

Upvotes: 0

Answers (3)

jvalli

Reputation: 721

Your problem is that when you detect a duplicate you generate a new number, but you never go back and check that the the newly generated number is not a duplicate of the numbers you already checked. When you run into a duplicate you'll need to reset the checking loop through some mechanism.

I fixed up the code to work around the problem, but it's not the prettiest solution. I also did some minor optimisation as you were looping through unnecessary indices.

import java.util.Random;

public class Prog433a {

    public static void main(String[] args) {

        Random randslct = new Random();

        int[] list = new int[20];
        int counter = 0;
        int index = 0;
        int min2 = 0;

        System.out.println("\nAfter");

        for(int k = 0; k < list.length - 1; k++) {

            list[k] = randslct.nextInt(30) + 1;
            boolean unique = true;
            for(int z = k - 1; z >= 0; z--) {
                if(list[k] == list[z]) {
                    if(list[k] == list[z]) {
                        unique = false;
                        break;
                    }
                }
            }
            if(!unique) {
                // Repeat last index
                --k;
            }
        }

        int min = list[0];
        while(counter < list.length - 1) {
            for(int x = 0; x < list.length - 1; x++) { // scroll through the indexes.
                if(list[x] < min) {
                    min = list[x];
                    index = x; // keep the index of the biggest number.
                }
            }
            System.out.println(list[index]);
            min = 100 * (list[index]);

            list[index] = 100 * (list[index]); // change the value in the original array so it won't find the same max again
            counter++;
        }

    }

}

Upvotes: 2

ctst

Reputation: 1680

Your mistake is when you try to add a new number. You just check, if it isn't the same as the one before, but not if it is the same as twice before. You can do this as follow:

boolean isDuplicate(int index, int[] list){
    for(int i=index-1; i>=0;i--){
        if(int[i]==int[index])
            return false
    }
    return true;
}

instead of your inner of the for-loop you can now write:

do{
    list[k] = randslct.nextInt(30) + 1;
}while(isDuplicate(k, list));

Also you should change your output, e.g. give the already written output a negative value and ignore negative values. If you want to change the numbers up to e.g. 200 your code now won't work.

Upvotes: 1

Prashant

Reputation: 5383

Lets take this by example. Consider that the current list that has been generated is:

list = [5, 7, 9, 3, 8, 9]

where 9 is the current number.

Now in the for-loop, you iterate from list[6] to list[0]. Here, in comparision, you come to 2nd index (list[2]) where the condition

list[k] == list[z] && z != k

turns out to be true and a new random number is generated. Lets assume that here the new random number that you generated is '8'. The loop terminates successfully and your array now has a duplicate.

Upvotes: 0

Checking for Duplicates in an Array Backwards

Answers (3)

Related Questions